ModRED: Hardware design and reconfiguration planning for a high dexterity modular self-reconfigurable robot for extra-terrestrial exploration

This paper presents a homogeneous modular robot system design based on four per-module degrees of freedom (DOF), including a prismatic DOF to increase the versatility of its reconfiguration and locomotion capabilities. The ModRED (Modular Robot for Exploration and Discovery) modules are developed with rotary-plate genderless single sided docking mechanisms (RoGenSiD) that allow chain-type configurations and lead towards hybrid-type configurations. Various locomotion gaits are simulated through the Webots robot simulator and implemented in the real ModRED system. This work also addresses the problem of dynamic reconfiguration in a modular self-reconfigurable robot (MSR). The self-reconfiguration problem is modeled as an instance of the graph-based coalition formation problem. We formulate the problem as a linear program that finds the “best” partition or coalition structure among a set of ModRED modules. The technique is verified experimentally for a variety of settings on an accurately simulated model of the ModRED robot within the Webots robot simulator. Our experimental results show that our technique can find the best partition with a reasonably low computational overhead.     

Multiagent control of self-reconfigurable robots

We demonstrate how multiagent systems provide useful control techniques for modular self-reconfigurable (metamorphic) robots. Such robots consist of many modules that can move relative to each other, thereby changing the overall shape of the robot to suit different tasks. Multiagent control is particularly well-suited for tasks involving uncertain and changing environments. We illustrate this approach through simulation experiments of Proteo, a metamorphic robot system currently under development.     

High-level motion planning for CPG-driven modular robots

Modular robots may become candidates for search and rescue operations or even for future space missions, as they can change their structure to adapt to terrain conditions and to better fulfill a given task. A core problem in such missions is the ability to visit distant places in rough terrain. Traditionally, the motion of modular robots is modeled using locomotion generators that can provide various gaits, e.g. crawling or walking. However, pure locomotion generation cannot ensure that desired places in a complex environment with obstacles will in fact be reached. These cases require several locomotion generators providing motion primitives that are switched using a planning process that takes the obstacles into account. In this paper, we present a novel motion planning method for modular robots equipped with elementary motion primitives. The utilization of primitives significantly reduces the complexity of the motion planning which enables plans to be created for robots of arbitrary shapes. The primitives used here do not need to cope with environmental changes, which can therefore be realized using simple locomotion generators that are scalable, i.e., the primitives can provide motion for robots with many modules. As the motion primitives are realized using locomotion generators, no reconfiguration is required and the proposed approach can thus be used even for modular robots without self-reconfiguration capabilities. The performance of the proposed algorithm has been experimentally verified in various environments, in physical simulations and also in hardware experiments.     

Network-based reconfiguration routes for a self-reconfigurable robot

This paper presents a network-based analysis approach for the reconfiguration problem of a self-reconfigurable robot. The self-reconfigurable modular robot named ＂AMOEBA-I＂ has nine kinds of non-isomorphic configurations that consist of a configuration network. Each configuration of the robot is defined to be a node in the weighted and directed configuration network. The transformation from one configuration to another is represented by a directed path with nonnegative weight. Graph theory is applied in the reconfiguration analysis, where reconfiguration route, reconfigurable matrix and route matrix are defined according to the topological information of these configurations. Algorithms in graph theory have been used in enumerating the available reconfiguration routes and deciding the best reconfiguration route. Numerical analysis and experimental simulation results prove the validity of the approach proposed in this paper. And it is potentially suitable for other self-reconfigurable robots＇ configuration control and reconfiguration planning.     

Configuration representation and reconfiguration optimization for the reconfigurable robots with independent manipulation

Single module of the reconfigurable robots with independent manipulation can perform the actions of locomotion and manipulation. In conformity with the request for achieving autonomous operation in the unstructurized environment instead of fixed operation in the structurized environment, these robots are applied in the complicated and dangerous environment. The existing researches on the configuration theory focus on the reconfigurable robots with limited locomotion and the ones with independent locomotion, not being applicable to the reconfigurable robots with independent manipulation. The vector configuration is put forward, the research content of which contains the topology and locomotion direction of configuration, the posture and orientation and connection relation between modules. Module state vector and configuration state matrix are proposed for representation methodology for the swarm configuration of these reconfigurable robots, which supports transformation operation to represent and trigger behavior motion of the module and reconfiguration between configurations. Optimization algorithm of assembly reconfiguration applying workload as the optimization target is presented, as well as optimization algorithm of transformation reconfiguration applying the integration of posture orientation workload and connection workload. The result of optimization is the relation of state transformation between the initial configuration and the object one as the basic of reconfiguration plan and control. Supported by the National High-Tech Research and Development Program of China (Grant No. 2006AA04Z254) and the Scientific Research Fund for Doctor of Liaoning Provice (Grant No. 20071007)     

The design of a representation and analysis method for modular self-reconfigurable robots

For Modular Self-Reconfigurable (MSR) robots to successfully reconfigure themselves, the control system must have the robot's topological structure before, during and after the reconfiguration process. Therefore, the module's docking status such as the docking orientation and the availability of docking ports must be ascertained before self-configuration takes place. This paper presents a representation method, based on labelled planar graphs and incidence matrices to represent the topologic structure of a group of connected modules. Essential information such as the orientations of the docked joints and docking ports are obtained from the labelled graph for reconfiguration. An innovative Hardware Orientation Detecting System (HODS) is proposed for detecting the orientation between two docking ports, which can be applied to all multi-orientation docking systems. An analytical method is also presented to determine whether a structure has enough degrees-of-freedom to perform self-reconfiguration.     

An optimal algorithm for two robots path planning problem on the grid

This paper is a study on the problem of path planning for two robots on a grid. We consider the objective of minimizing the maximum path length which corresponds to minimizing the arrival time of the last robot at its goal position. We propose an optimal algorithm that solves the problem in linear time with respect to the size of the grid. We show that the algorithm is complete; meaning that it is sure to find an optimal solution or report if any does not exist.     

Dynamic and stable reconfiguration of self-reconfigurable planar parallel robots

This paper discusses dynamic and stable reconfigurations of self-reconfigurable planar parallel robots that can be done by coupling and decoupling of two underactuated robots on a horizontal plane. The limbs of the parallel robots are 2R open kinematic chains with their second joints unactuated. Two types of self-reconfigurable parallel robots are considered. One is formed by two limbs, and the other is by a limb and an underactuated robot consisting of two limbs and a platform. Uncertainty singularities enable them to self-reconfigure without additional actuators at their coupling mechanism. In this paper, we propose dynamic contact motion control to move them from an initial contact configuration to an uncertainty singular configuration while maintaining their contact. This paper also considers dynamic stability at their uncertainty singularities as equilibrium and shows that there exist geometrically stable configurations without feedback control, which are useful for decoupling. Experiments with real robots are carried out to verify the effectiveness of the dynamic contact motion control and stability analysis.     

Dual hierarchical genetic-optimal control: A new global optimal path planning method for robots

A new two-stage analytical-evolutionary algorithm considering dynamic equations is presented to find global optimal path. The analytical method is based on the indirect open loop optimal control problem and the evolutionary method is based on genetic algorithm (GA). Initial solutions, as start points of optimal control problem, are generated by GA to be used by optimal control. Then, a new sub-optimal path is generated through optimal control. The cost function is calculated for every optimal solution and the best solutions are chosen for the next step. The obtained path is used by GA to produce new generation of start points. This process continues until the minimum cost value is achieved. In addition, a new GA operator is introduced to be compatible with optimal control. It is used to select the pair chromosomes for crossover. The proposed method eliminates the problem of optimal control (being trapped in locally optimal point) and problem of GA (lack of compatibility with analytical dynamic equations). Hence problem is formulated and verification is done by comparing the results with a recent work in this area. Furthermore effectiveness of the method is approved by a simulation study for spatial non-holonomic mobile manipulators through conventional optimal control and the new proposed algorithm.     

Distributed reconfiguration of metamorphic robot chains

The problem we address is the distributed reconfiguration of a planar metamorphic robotic system composed of any number of hexagonal modules. After presenting a framework for classifying motion planning algorithms for metamorphic robotic systems, we describe distributed algorithms for reconfiguring a straight chain of hexagonal modules to any intersecting straight chain configuration. We prove our algorithms are correct, and show that they are either optimal or asymptotically optimal in the number of moves and asymptotically optimal in the time required for parallel reconfiguration.Received: 28 October 2002, Accepted: 31 October 2003, Published online: 1 March 2004 Corresdpondence to: Jennifer E. WalterNancy M. Amato: amato]@cs.tamu.edu A preliminary version of this paper appeared in the Proc. of the 19th ACM Symposium on Principles of Distributed Computing, July 2000, pages 171-180. The work of N. Amato and J. Walter was supported in part by NSF CAREER Award CCR-9624315, NSF Grants IIS-9619850, ACI-9872126, EIA-9975018, EIA-0103742, EIA-9805823, ACR-0081510, ACR-0113971, CCR-0113974, EIA-9810937, EIA-0079874, by the Texas Higher Education Coordinating Board grant ARP-036327-017, and by the DOE ASCI ASAP program grant B347886. The work of J. Walter was supported in part by Department of Education GAANN and GE Faculty of the Future fellowships.     

广义Voronoi图求解多机器人运动规划

在拥挤环境中,由于障碍物的边界形状比较复杂,需要使用广义Voronoi图表示空间环境。且在多移动机器人的运动规划过程中,需要协调多个机器人的运动,必须得到Voronoi图通道的宽度。为此提出了一种计算拥挤障碍物环境中生成的广义Voronoi图及其通道宽度的算法。并在生成的Voronoi图上利用A*算法对多个机器人进行路径规划,并利用分布式方法协调多个机器人运动。对协调两个机器人运动的过程进行了仿真,仿真结果表明利用提出的算法生成的具有通道宽度信息的Voronoi图能够满足多移动机器人运动规划的需要。     

Scalable multi-radio communication in modular robots

Decentralized control of self-reconfiguring modular robots requires reliable inter-module communication. Communication links must tolerate module misalignment and implement the neighbor-to-neighbor communication model. In this paper, we propose a wireless system based on multiple radios per module that addresses these challenges. Although the capacity of general wireless mesh networks is known to rapidly decrease with network size, we show that a multi-radio single-channel system has constant capacity in square and cubic lattices of infinite size. We validate the performance of such a system in a testbed with 15 unactuated modules using synthetic data and a benchmark decentralized algorithm. We also demonstrate automatic neighbor detection. The main benefits of radio communication in modular robots are tolerance to module misalignment and to eliminate the tight coupling between communication and mechanical design necessitated by typical existing infrared and wired systems. Our results are the first to establish the feasibility of radio as the primary means of inter-module communication in modular robots.     

基于环境分层方法的双足机器人路径规划研究

为了实现双足机器人在障碍环境中的路径规划,提出一种将三维环境分层的方法,用两个截面将环境分为高于机器人身高障碍层、低于机器人抬脚高度障碍层和中间障碍层.首先在中间障碍层进行机器人轨迹规划,再根据机器人各种步态的不同损耗构建代价函数,把规划好的轨迹放到最底层进行规划修改,最终得到双足机器人在规划路径上代价最小的一系列连续的动作,通过计算机仿真实验验证了方法的有效性.     

A global motion planner that learns from experience for autonomous mobile robots

A new technique for enhancing global path planning for mobile robots working in partially known as indoor environments is presented in this paper. The method is based on a graph approach that adapts the cost of the paths by incorporating travelling time from real experiences. The approach uses periodical measurements of time and position reached by the robot while moving to the goal to modify the costs of the branches. Consequently, the search of a feasible path from a static global map in dynamic environments is more realistic than employing a distance metric. Our approach has been tested in simulation as well on an autonomous robot. Results from both simulation and real experiences are discussed.     

Complete coverage path planning for wheeled agricultural robots

In the agricultural industry, an evolutionary effort has been made over the last two decades to achieve precise autonomous systems to perform typical in-field tasks, including harvesting, mowing, and spraying. One of the main objectives of an autonomous system in agriculture is to improve the efficiency while reducing the environmental impact and cost. Due to the nature of these operations, complete coverage path planning (CCPP) approaches play an essential role to find an optimal path which covers the entire field while taking into account land topography, operation requirements, and robot characteristics. The aim of this paper is to propose a CCPP approach defining the optimal movements of mobile robots over an agricultural field. First, a method based on tree exploration is proposed to find all potential solutions satisfying some predefined constraints. Second, a similarity check and selection of optimal solutions method is proposed to eliminate similar solutions and find the best solutions. The optimization goals are to maximize the coverage area and to minimize overlaps, nonworking path length, and overall travel time. To explore a wide range of possible solutions, our approach is able to consider multiple entrances for the robot. For fields with a complex shape, different dividing lines to split them into simple polygons are also considered. Our approach also computes the headland zones and covers them automatically which leads to a high coverage rate of the field.     

On the complexity of case-based planning

This paper analyses the computational complexity of problems related to case-based planning: planning when a plan for a similar instance is known, and planning from a library of plans. It is proven that planning from a single case has the same complexity than generative planning (i.e. planning ‘from scratch’); using an extended definition of cases, complexity is reduced if the domain stored in the case is similar to the one to search plans for. Planning from a library of cases is shown to have the same complexity. In both cases, the complexity of planning remains, in the worst case, PSPACE-complete.     

轮手一体机器人能量次优重构规划方法

模块化机器人的重构规划中,由于各模块的目标分配与其轨迹规划之间的耦合关系导致组合爆炸问题.本文提出一种基于简化模型的能量次优规划方法,将重构规划问题转化为最优控制问题,实现目标分配与轨迹规划的解耦.通过求解由Hamilton-Jacobi-Bellman（HJB）方程描述的最优控制问题,得到简化模型的值函数和最优轨迹.各模块的运动目标由值函数的吸引域决定.通过在最优轨迹附近的次优区域内搜索得到实际运动轨迹,提高了搜索效率.仿真实验结果表明,该方法能够选择合适的模块组合,并能在障碍物环境中生成满足机器人动力学约束的运动轨迹.     

Nonholonomic multibody mobile robots: Controllability and motion planning in the presence of obstacles

We consider mobile robots made of a single body (car-like robots) or several bodies (tractors towing several trailers sequentially hooked). These robots are known to be nonholonomic, i.e., they are subject to nonintegrable equality kinematic constraints involving the velocity. In other words, the number of controls (dimension of the admissible velocity space), is smaller than the dimension of the configuration space. In addition, the range of possible controls is usually further constrained by inequality constraints due to mechanical stops in the steering mechanism of the tractor. We first analyze the controllability of such nonholonomic multibody robots. We show that the well-known Controllability Rank Condition Theorem is applicable to these robots even when there are inequality constraints on the velocity, in addition to the equality constraints. This allows us to subsume and generalize several controllability results recently published in the Robotics literature concerning nonholonomic mobile robots, and to infer several new important results. We then describe an implemented planner inspired by these results. We give experimental results obtained with this planner that illustrate the theoretical results previously developed.This research was partially funded by DARPA contract DAAA21-89-C0002 (Army), CIFE (Center for Integrated Facility Engineering), and Digital Equipment Corporation.     

A simple approach to the control of locomotion in self-reconfigurable robots

In this paper we present role-based control which is a general bottom-up approach to the control of locomotion in self-reconfigurable robots. We use role-based control to implement a caterpillar, a sidewinder, and a rolling track gait in the CONRO self-reconfigurable robot consisting of eight modules. Based on our experiments and discussion we conclude that control systems based on role-based control are minimal, robust to communication errors, and robust to reconfiguration.