Simulation and control of distributed robot search teams

This article describes the simulation of distributed autonomous robots for search and rescue operations. The simulation system is utilized to perform experiments with various control strategies for the robot team and team organizations, evaluating the comparative performance of the strategies and organizations. The objective of the robot team is to, once deployed in an environment (floor-plan) with multiple rooms, cover as many rooms as possible. The simulated robots are capable of navigation through the environment, and can communicate using simple messages. The simulator maintains the world, provides each robot with sensory information, and carries out the actions of the robots. The simulator keeps track of the rooms visited by robots and the elapsed time, in order to evaluate the performance of the robot teams. The robot teams are composed of homogenous robots, i.e., identical control strategies are used to generate the behavior of each robot in the team. The ability to deploy autonomous robots, as opposed to humans, in hazardous search and rescue missions could provide immeasurable benefits.     

Evolving non-trivial behaviors on real robots: A garbage collecting robot

Recently, a new approach involving a form of simulated evolution has been proposed to build autonomous robots. However, it is still not clear if this approach is adequate for real life problems. In this paper we show how control systems that perform a non-trivial sequence of behaviors can be obtained with this methodology by “canalizing” the evolutionary process in the right direction. In the experiment described in the paper, a mobile robot was successfully trained to keep clear an arena surrounded by walls by locating, recognizing, and grasping “garbage” objects and by taking collected objects outside the arena. The controller of the robot was evolved in simulation and then downloaded and tested on the real robot. We also show that while a given amount of supervision may canalize the evolutionary process in the right direction the addition of unnecessary constraints can delay the evolution of the desired behavior.     

A fault-tolerant approach to robot teams

As the applications of mobile robotics evolve it has become increasingly less practical for researchers to design custom hardware and control systems for each problem. This paper presents a new approach to control system design in order to look beyond end-of-lifecycle performance, and consider control system structure, flexibility, and extensibility. Towards these ends the Control ad libitum philosophy was proposed, stating that to make significant progress in the real-world application of mobile robot teams the control system must be structured such that teams can be formed in real-time from diverse components. The Control ad libitum philosophy was applied to the design of the HAA (Host, Avatar, Agent) architecture: a modular hierarchical framework built with provably correct distributed algorithms. A control system for mapping, exploration, and foraging was developed using the HAA architecture and evaluated in three experiments. First, the basic functionality of the HAA architecture was studied, specifically the ability to: (a) dynamically form the control system, (b) dynamically form the robot team, (c) dynamically form the processing network, and (d) handle heterogeneous teams and allocate robots between tasks based on their capabilities. Secondly, the control system was tested with different rates of software failure and was able to successfully complete its tasks even when each module was set to fail every 0.5–1.5 min. Thirdly, the control system was subjected to concurrent software and hardware failures, and was still able to complete a foraging task in a 216 m² environment.     

Evolving neural controllers that elicit nontrivial behaviors using a developmental process

Recently, evolutionary robotics (ER) has been attracting a lot of attention in the field of robotics artificial life and so on. ER approaches are expected to provide feasible methods to design controllers for autonomous mobile robots with less human intervention. However, most of the conventional studies in ER have been aiming at obtaining very simple (trivial) behaviors such as obstacle avoiding, wall following, and target approaching. To make the ER approach more fruitful, we should pay close attention to obtaining nontrivial behaviors. Based on these considerations, in this paper we propose a method for obtaining nontrivial behaviors using a developmental process with a carefully arranged grafting method. To verify the validity, we apply our idea to the construction of neural controllers that can cope with rough terrain. This work was presented, in part, at the Third International Symptosium on Artificial Life and Robotics, Oita, Japan, January 19–21, 1998     

A prototype autonomous robot for underwater crime scene investigation and emergency response

Underwater crime scene investigation and emergency response are tasks typically carried out by divers constituting part of a specialist team. Operating in such dynamic environments, often with poor visibility and risk of concealed hazards, can be time consuming and dangerous. Autonomous uncrewed vessels with underwater acoustic imaging sensors have been used for similar purposes in other fields (e.g., hydrography, naval mine countermeasures [MCMS], etc.) but have not been adopted in this specific application domain. The Police Robot for Inspection and Mapping of underwater Evidence (PRIME) is an autonomous uncrewed surface vessel that is being developed for this purpose. It is a novel application of existing robotic technology that is intended to be used within an end-to-end police and emergency underwater search process. It aims to enhance the effectiveness, efficiency, and safety of divers by autonomously locating and highlighting target objects or regions of interest, as well as benign regions, thereby reducing their time spent underwater. Side-scan imaging sonars are used to sense the underwater environment using techniques leveraged from the similar application domain of naval MCMs. The system autonomously generates actionable intelligence in the form of simplified coverage and anomaly maps for easy interpretation by the dive team. These are communicated to shore in real-time and georeferenced on satellite maps. This paper details the PRIME system prototype and presents results from initial field experimentation. The prototype has been operated in various urban, shallow-water environments. The experimental results shown here were collected in Bristol Harbour (the UK) with a water depth of approximately 5 m. In the experiment, a clothed mannequin resembling a human body was deployed on the muddy floor. Autonomous searches were executed and the body was detected successfully as an anomaly against the background, illustrating the feasibility and viability of the system as an autonomous robotic aid for locating missing persons in a representative, unstructured, and dynamic real-world environment.     

Evolutionary control of bipedal locomotion in a high degree-of-freedom humanoid robot: first steps

This article describes a methodology, together with an associated series of experiments employing this methodology, for the evolution of walking behavior in a simulated humanoid robot with up to 20 degrees of freedom. The robots evolved in this study learn to walk smoothly in an upright or near-upright position and demonstrate a variety of different locomotive behaviors, including “skating,” “limping,” and walking in a manner curiously reminiscent of a mildly or heavily intoxicated person. A previous study demonstrated the possible potential utility of this approach while evolving controllers based on simulated humanoid robots with a restricted range of movements. Although walking behaviors were developed, these were slow and relied on the robot walking in an excessively stooped position, similar to the gait of an infirm elderly person. This article extends the previous work to a robot with many degrees of freedom, up to 20 in total (arms, elbows, legs, hips, knees, etc.), and demonstrates the automatic evolution of fully upright bipedal locomotion in a humanoid robot using an accurate physics simulator. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

一种移动机器人的禁忌搜索自主导航算法

纯粹的反应式导航算法在复杂未知环境下易陷入局部极小,为此提出一种基于局部子目标和禁忌搜索的自主导航算法．以当前可视区域内障碍物的关键角点为搜索邻域,利用禁忌搜索算法执行优化操作生成当前子目标,进而采用反应式导航算法对其进行跟踪,最终通过子目标的动态切换引导机器人驶达目标位置．算法可有效克服局部极小,显著提高机器人在复杂环境下的自主性．理论分析和仿真实验验证了算法的可行性和有效性．     

Swarm robotics search & rescue: A novel artificial intelligence-inspired optimization approach

In this paper, a novel heuristic algorithm is proposed to solve continuous non-linear optimization problems. The presented algorithm is a collective global search inspired by the swarm artificial intelligent of coordinated robots. Cooperative recognition and sensing by a swarm of mobile robots have been fundamental inspirations for development of Swarm Robotics Search & Rescue (SRSR). Swarm robotics is an approach with the aim of coordinating multi-robot systems which consist of numbers of mostly uniform simple physical robots. The ultimate aim is to emerge an eligible cooperative behavior either from interactions of autonomous robots with the environment or their mutual interactions between each other. In this algorithm, robots which represent initial solutions in SRSR terminology have a sense of environment to detect victim in a search & rescue mission at a disaster site. In fact, victim’s location refers to global best solution in SRSR algorithm. The individual with the highest rank in the swarm is called master and remaining robots will play role of slaves. However, this leadership and master position can be transitioned from one robot to another one during mission. Having the supervision of master robot accompanied with abilities of slave robots for sensing the environment, this collaborative search assists the swarm to rapidly find the location of victim and subsequently a successful mission. In order to validate effectiveness and optimality of proposed algorithm, it has been applied on several standard benchmark functions and a practical electric power system problem in several real size cases. Finally, simulation results have been compared with those of some well-known algorithms. Comparison of results demonstrates superiority of presented algorithm in terms of quality solutions and convergence speed.     

Optimization of interval type-2 fuzzy logic controllers for a perturbed autonomous wheeled mobile robot using genetic algorithms

We describe a tracking controller for the dynamic model of a unicycle mobile robot by integrating a kinematic and a torque controller based on type-2 fuzzy logic theory and genetic algorithms. Computer simulations are presented confirming the performance of the tracking controller and its application to different navigation problems.     

Evolving hierarchical robot behaviours

Inspired by the work of Brooks, many researchers involved in programming robots have turned to the behaviour-based approach. At present, the behaviours are designed by hand and hard-wired into the architecture. The work presented in this paper looks at using an evolutionary algorithm approach (based on the genetic algorithm) to construct behaviours. Building from well-defined primitive behaviours, hierarchies can be evolved to produce more complex behaviour. The behaviours in the evolutionary system are tested in simulation, but the best are then tested on a mobile robot for grounding in the real world. This allows the evolutionary process to rapidly drive the development of the behaviours using simulation while also ensuring their suitability in the real world. In the paper we show how this evolutionary process evolves practical hierarchical behaviours for the detection of a goal object in a series of mazes.     

Design of an autonomous agricultural robot

This paper presents a state-of-the-art review in the development of autonomous agricultural robots including guidance systems, greenhouse autonomous systems and fruit-harvesting robots. A general concept for a field crops robotic machine to selectively harvest easily bruised fruit and vegetables is designed. Future trends that must be pursued in order to make robots a viable option for agricultural operations are focused upon.A prototype machine which includes part of this design has been implemented for melon harvesting. The machine consists of a Cartesian manipulator mounted on a mobile chassis pulled by a tractor. Two vision sensors are used to locate the fruit and guide the robotic arm toward it. A gripper grasps the melon and detaches it from the vine. The real-time control hardware architecture consists of a blackboard system, with autonomous modules for sensing, planning and control connected through a PC bus. Approximately 85% of the fruit are successfully located and harvested.     

Evolving gaits for hexapod robots using cyclic genetic algorithms

A major facet of multi-legged robot control is locomotion. Each leg must move in such a manner that it efficiently produces thrust and provides maximum support. The motion of all the legs must be coordinated so that they are working together to provide constant stability while propelling the robot forward. In this paper, we discuss the use of a cyclic genetic algorithm (CGA) to evolve control programs that produce gaits for actual hexapod robots. Tests done in simulation and verified on the actual robot show that the CGA successfully produces gaits for both fully capable and disabled robots.     

A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment

The single-robot search problem in an unknown environment is defined as the problem of finding a stationary object in the environment whose map is not known a priori. Compared to exploration, the only difference lies in goal selection as the objectives of search and exploration are dissimilar, i.e. a trajectory that is optimal in exploration does not necessarily minimize the expected value of the time to find an object along it. For this reason, in this paper we extend the preliminary ideas presented in Kulich et al. [1] to a general framework that accounts for the particular characteristics of the search problem. Within this framework, an important decision involved in the determination of the trajectory can be formulated as an instance of the Graph Search Problem (GSP), a generalization of the well-known Traveling Deliveryman Problem (TDP) which has not received much attention in the literature. We developed a tailored Greedy Randomized Adaptive Search Procedure (GRASP) meta-heuristic for the GSP, which generates good quality solutions in very short computing times and is incorporated in the overall framework. The proposed approach produces very good results in a simulation environment, showing that it is feasible from a computational standpoint and the proposed strategy outperforms the standard approaches.     

Evolution of low-complexity neural controllers based on multiobjective evolution

In this paper, we present a new method based on multiobjective evolutionary algorithms to evolve low-complexity neural controllers for agents that have to perform multiple tasks simultaneously. In our method, each task and the structure of the neural controller are considered as separated objective functions. We compare the results of two different encoding schemes: (1) connectionist encoding, and (2) node-based encoding. The results show that multiobjective evolution can be successfully applied to generate low-complexity neural controllers. In addition, node-based encoding outperformed connectionist encoding in terms of agent performance and the robustness of the neural controller. This work was presented in part at the 12th International Symposium on Artificial Life and Robotics, Oita, Japan, January 25–27, 2007     

Evolutionary path planning for robot assisted part handling in sheet metal bending

While the bending sequence planning has been intensively studied, design of the motion path of a sheet metal part in the bending operation tends to be ignored by researchers. Because during the bending operation, the space for maneuvering a sheet metal part is very small, collisions between the part and bending tools are likely to occur. When a robot is used to handle the part, the role of an automatic path-planning tool becomes more significant. In this study, an evolutionary path-planning approach for robot-assisted handling of sheet metal parts in bending is firstly proposed and implemented. The proposed approach globally searches the motion path space to identify feasible paths. Collision detection algorithms based on segment intersection are used to check if the generated paths are feasible or infeasible. This method can automatically design feasible handling operations for a robot. Simulation examples on a simple “V” shaped part and a part with multiple bents demonstrate that the approach is efficient and practical.     

Modeling gossip-based content dissemination and search in distributed networking

This paper presents a rigorous analytic study of gossip-based message dissemination schemes that can be employed for content/service dissemination or discovery in unstructured and distributed networks. When using random gossiping, communication with multiple peers in one gossiping round is allowed. The algorithms studied in this paper are considered under different network conditions, depending on the knowledge of the state of the neighboring nodes in the network. Different node behaviors, with respect to their degree of cooperation and compliance with the gossiping process, are also incorporated. From the exact analysis, several important performance metrics and design parameters are analytically determined. Based on the proposed metrics and parameters, the performance of the gossip-based dissemination or search schemes, as well as the impact of the design parameters, are evaluated.     

An interactive tool for mobile robot motion planning

This paper presents an interactive tool aimed at facilitating the understanding of several well-known algorithms and techniques involved in solving mobile robot motion problems. These range from those modelling the mechanics of mobility to those used in navigation. The tool focuses on describing these problems in a simple manner in order to be useful for education purposes among different disciplines. By highlighting interactivity, the tool provides a novel means to study robot motion planning ideas in a manner that enhances full understanding. Furthermore, the paper discuses how the tool can be used in an introductory course of mobile robotics.     

Dual-coding representations for robot vision programming in Tekkotsu

We describe complementary iconic and symbolic representations for parsing the visual world. The iconic pixmap representation is operated on by an extensible set of “visual routines” (Ullman, 1984; Forbus et al., 2001). A symbolic representation, in terms of lines, ellipses, blobs, etc., is extracted from the iconic encoding, manipulated algebraically, and re-rendered iconically. The two representations are therefore duals, and iconic operations can be freely intermixed with symbolic ones. The dual-coding approach offers robot programmers a versatile collection of primitives from which to construct application-specific vision software. We describe some sample applications implemented on the Sony AIBO. David S. Touretzky is a Research Professor in the Computer Science Department and the Center for the Neural Basis of Cognition at Carnegie Mellon University. He earned his B.A. in Computer Science from Rutgers University in 1978, and his M.S. (1979) and Ph.D. (1984) in Computer Science from Carnegie Mellon. Dr. Touretzky’s research interests are in computational neuroscience, particularly representations of space in the rodent hippocampus and related structures, and high level primitives for robot programming. He is presently developing an undergraduate curriculum in cognitive robotics based on the Tekkotsu software framework described in this article. Neil S. Halelamien earned a B.S. in Computer Science and a B.S. in Cognitive Science at Carnegie Mellon University in 2004, and is currently pursuing his Ph.D. in the Computation & Neural Systems program at the California Institute of Technology. His research interests are in studying vision from both a computational and biological perspective. He is currently using transcranial magnetic stimulation to study visual representations and information processing in visual cortex. Ethan J. Tira-Thompson is a graduate student in the Robotics Institute at Carnegie Mellon University. He earned a B.S. in Computer Science and a B.S. in Human-Computer Interaction in 2002, and an M.S. in Robotics in 2004, at Carnegie Mellon. He is interested in a wide variety of computer science topics, including machine learning, computer vision, software architecture, and interface design. Ethan’s research has revolved around the creation of the Tekkotsu framework to enable the rapid development of robotics software and its use in education. He intends to specialize in mobile manipulation and motion planning for the completion of his degree. Jordan J. Wales is completing a Master of Studies in Theology at the University of Notre Dame. He earned a B.S. in Engineering (Swarthmore College, 2001), an M.Sc. in Cognitive Science (Edinburgh, UK, 2002), and a Postgraduate Diploma in Theology (Oxford, UK, 2003). After a year as a graduate research assistant in Computer Science at Carnegie Mellon, he entered the master’s program in Theology at Notre Dame and is now applying to doctoral programs. His research focus in early and medieval Christianity is accompanied by an interest in medieval and modern philosophies of mind and their connections with modern cognitive science. Kei Usui is a masters student in the Robotics Institute at Carnegie Mellon University. He earned his B.S. in Physics from Carnegie Mellon University in 2005. His research interests are reinforcement learning, legged locomotion, and cognitive science. He is presently working on algorithms for humanoid robots to maintain balance against unexpected external forces.     

Using roadmaps to classify regions of space for autonomous robot navigation

The roadmap approach to robot path planning is one of the earliest methods. Since then, many different algorithms for building roadmaps have been proposed and widely implemented in mobile robots but their use has always been limited to planning in static, totally known environments. In this paper we combine the use of dynamic analogical representations of the environment with an efficient roadmap extraction method, to guide the robot navigation and to classify the different regions of space in which the robot moves. The paper presents the general reference architecture for the robotic system and then focuses on the algorithms for the construction of the roadmap, the classification of the regions of space and their use in robot navigation. Experimental results indicate the applicability and robustness of this approach in real situations.