«Submitted to the Department of Electrical Engineering and Computer Science in partial ful llment of the requirements for the degree of Doctor of ...»
Heterogeneous Multi-Robot Cooperation
Lynne E. Parker
Submitted to the Department of Electrical Engineering and
in partial ful llment of the requirements for the degree of
Doctor of Philosophy
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
c Massachusetts Institute of Technology 1994
All rights reserved.
Heterogeneous Multi-Robot Cooperation
Lynne E. Parker
Submitted to the Department of Electrical Engineering and Computer Science on January 7, 1994, in partial ful llment of the requirements for the degree of Doctor of Philosophy Abstract This report addresses the problem of achieving fault tolerant cooperation within smallto medium-sized teams of heterogeneous mobile robots. I describe a software architecture I have developed, called ALLIANCE, that facilitates robust, fault tolerant cooperative control, and examine numerous issues in cooperative team design. ALLIANCE is a fully distributed architecture that utilizes adaptive action selection to achieve cooperative control in robot missions involving loosely coupled, largely independent tasks. The robots in this architecture possess a variety of high-level functions that they can perform during a mission, and must at all times select an appropriate action based on the requirements of the mission, the activities of other robots, the current environmental conditions, and their own internal states. Since such cooperative teams often work in dynamic and unpredictable environments, the software architecture allows the team members to respond robustly and reliably to unexpected environmental changes and modi cations in the robot team that may occur due to mechanical failure, the learning of new skills, or the addition or removal of robots from the team by human intervention. In addition, an extended version of ALLIANCE, called L-ALLIANCE, incorporates a simple mechanism that allows teams of mobile robots to learn from their previous experiences with other robots, allowing them to select their own actions more e ciently on subsequent trials when working with \familiar" robots on missions composed of independent tasks. This mechanism allows a human system designer to easily and quickly group together the appropriate combination of robots for a particular mission, since robots need not have a priori knowledge of their teammates.
The development of ALLIANCE and L-ALLIANCE involved research on a number of topics: fault tolerant cooperative control, adaptive action selection, distributed control, robot awareness of team member actions, improving e ciency through learning, inter-robot communication, action recognition, and local versus global control. This report describes each of these topics in detail, along with experimental results of investigating these issues both in simulated and in physical mobile robot teams.
I am not aware of any other cooperative control architecture that has exhibited the combination of fault tolerance, reliability, adaptivity, and e ciency possible with ALLIANCE and L-ALLIANCE, and which has been successfully demonstrated on physical mobile robot teams.
Thesis Supervisor: Rodney A. Brooks Title: Professor of Computer Science Acknowledgements I express my heartfelt thanks to my thesis advisor, Rod Brooks, who supported and encouraged me throughout my time at MIT. He provided a good mixture of guidance and non-interference, allowing me to explore and develop my own ideas while o ering helpful suggestions when they were most needed. I learned much from him about developing ideas and making them work. I also sincerely thank Lynn Stein, who served as one of my thesis readers, for her many helpful suggestions and critiques of my thesis work. Her advice improved my thesis in many areas. Thanks also to Patrick Winston, my third thesis reader, not only for his encouragement during my stay at MIT, but also for his guidance of the AI Lab, which has been a great source of inspiration to me.
I have very much enjoyed being a part of the Mobot Lab. In particular, I have enjoyed discussing various cooperative robotics topics with Maja Mataric, and to commiserate with her when our robots refused to behave. Anita Flynn has been a constant source of encouragement and inspiration, which I greatly appreciate. I o er a special thanks to Ian Horswill for his willingness to o er hacking assistance when needed, to Matt Marjonovic for his e orts on the robots' radio communication system, and to Mike Connell for his e orts in building the R-2s. Three visiting scientists to the Mobot Lab from Japan also provided much help and friendship: Masa Konishi, from the Mazda Motor Corporation, who worked with me on the Seymour robot during my early days at MIT, Yasuo Kagawa, also from Mazda, who built the rst version of the multi-robot simulator that I used, and Macky Yamamoto, from Matsushita Research Institute, who was very helpful in debugging the R-2's. I thank all three for their assistance.
While at MIT, I have enjoyed the company of many other AI Lab members, including Joanna Bryson, Tina Kapur, Tanveer Mahmood, Nancy Pollard, Sajit Rao, Aparna Ratan, Jose Robles, Karen Sarachik, Pawan Sinha, Mark Torrance, and Holly Yanco. Many of these people proofed papers, critiqued practice talks, or o ered other valuable advice, for which I am grateful. Thanks also to Eric Grimson, who was extremely supportive and encouraging as my academic counselor.
I appreciate the help, patience, and friendliness of IS Robotics' personnel Chuck Rosenberg, Helen Griner and Peter Ning in providing me with working and communicating R-2's and Genghis-II. Although I was not thrilled with the time delays in receiving functional robots, the delays were mostly caused by circumstances out of v their control, and were certainly not from lack of e ort on their part. Their services saved me from months (years?) of tedious robot-building on my own, and for that I am truly grateful.
While living in the Boston area, my husband and I have been fortunate to meet a number of fellow \transplants from the South," | in particular, Alice and Je Hill, Pam and Terry Wright, and Carol and Jon Long | who provided a muchneeded escape from the pressures of MIT, and whose companionship we have greatly enjoyed. Although we four couples are scattering across the country now, we have become lifelong friends.
Finally, I express my gratitude for my family | my parents, sister, brother, and grandparents | who believed in me, o ered guidance, and supported my decisions no matter what. Most of all, I o er my deepest thanks to my husband Bob for agreeing to move to Boston so that I could pursue this degree, and for supporting me and encouraging me all along the way. He brings immense happiness to my life with his never ending love and devotion, and thus I dedicate this dissertation to him.
LIST OF TABLESxviii Chapter 1 Introduction A key driving force in the development of mobile robotic systems is their potential for reducing the need for human presence in dangerous applications, such as the cleanup of toxic waste, nuclear power plant decommissioning, extra-planetary exploration, search and rescue missions, and security, surveillance, or reconnaissance tasks or in repetitive types of tasks, such as automated manufacturing or industrial/household maintenance. The nature of many of these challenging work environments requires the robotic systems to work fully autonomously in achieving human-supplied goals.
One approach to designing these autonomous systems is to develop a single robot that can accomplish particular goals in a given environment. However, the complexity of many environments or missions may require a mixture of robotic capabilities that is too extensive to design into a single robot. Additionally, time constraints may require the use of multiple robots working simultaneously on di erent aspects of the mission in order to successfully accomplish the objective. In some instances, it may actually be easier or cheaper to design cooperative teams of robots to perform some mission than it would be to use a single robot. Thus, we must build teams of possibly heterogeneous robots that can work together to accomplish a mission that no individual robot can accomplish alone.
This report addresses the problem of achieving fault tolerant cooperation within small- to medium-sized teams of heterogeneous mobile robots (say, 2 to 10 robots) by constructing a software architecture, called ALLIANCE, that facilitates cooperative control, and by studying numerous issues in cooperative team design. ALLIANCE is a fully distributed architecture that utilizes adaptive action selection to achieve cooperative control in robot missions involving loosely coupled, largely independent subtasks. The robots in this architecture possess a variety of high-level functions that they can perform during a mission, and must at all times select an appropriate action based on the requirements of the mission, the activities of other robots, the current environmental conditions, and their own internal states. Since such cooperative teams
CHAPTER 1. INTRODUCTIONoften work in dynamic and unpredictable environments, the software architecture allows the robot team members to respond robustly, reliably, exibly, and coherently to unexpected environmental changes and modi cations in the robot team that may occur due to mechanical failure, the learning of new skills, or the addition or removal of robots from the team by human intervention. In addition, I present an extended version of ALLIANCE, called L-ALLIANCE, that uses a dynamic parameter update mechanism to allow teams of robots to learn from their previous experiences with other robots, and to select their own actions more e ciently on subsequent trials when working with \familiar" robots.
1.1 Cooperative Example: Hazardous Waste Cleanup On April 26, 1986, at 1:23 AM, the worst civilian nuclear power accident in history occurred at the Chernobyl power station in Ukraine, U.S.S.R. Woodru, 1988]. The nuclear reactor was destroyed by an explosion brought on by a series of human operator errors in performing a test, with the resulting graphite re in the reactor core leading to the contamination of large areas surrounding the plant, requiring the evacuation of 135,000 people. More than two hundred re ghters and on-site personnel were treated for acute radiation sickness, and many died from direct exposure during the initial emergency response. Although automated solutions to site evaluation were attempted, nearly all of the work performed in containing the disaster had to be carried out by humans, many of whom literally sacri ced their lives to stabilize the reactor.
If teams of robots could have been sent into the Chernobyl power station instead of teams of humans, many lives could have been saved. However, the robotics community clearly has a long way to go before we can deal with such applications in which the environment and the capabilities of the robots vary dynamically from moment to moment. A situation as dangerous as that presented at Chernobyl is an ideal application for groups of heterogeneous robots working together to accomplish a mission that is too hazardous for humans. However, notwithstanding the non-trivial radiation-hardening advances needed to allow robots to perform in these environments, many advances must also be made in the software control systems of such robotic teams. This report addresses many of these software control issues of A German remote-controlled robot was sent to the site to help with the cleanup Press, 1986], but it failed immediately, presumably due to radiation bombardment. Supposedly a last resort, a small radio-controlled toy car, altered to carry a video camera, turned out to be the most useful automated solution for relaying information to the humans from the remote location.
1.1. COOPERATIVE EXAMPLE: HAZARDOUS WASTE CLEANUP 3cooperative robotics that are necessary to achieve this ultimate goal of fault tolerant cooperation in dynamic environments.
A tremendously simpli ed analog of the Chernobyl application is used here as a descriptive example of the type of cooperation I wish to achieve. Consider the mission illustrated in gure 1-1, in which an arti cial hazardous waste spill in a 2 large indoor area must be cleaned up. In this case, the spill consists of a number of small cylindrical objects clustered in one area of the room. I pretend that the spill is dangerous enough that we prefer to avoid the risk of human exposure to toxins, and opt instead to use an automated solution. The mission requires rst nding the spill and then moving it to a safe location in the room where we assume the hazardous material can be dealt with more easily by humans. The mission also requires the team to periodically report its progress to the humans monitoring the system by radioing a message from the room entrance. If the monitoring human determines that su cient progress is not being made, the human sends in another robot or robots to help with the mission.
A di culty in this mission is that the human monitor does not know the exact location of the spill in robot coordinates, and can only give the robots qualitative information on the initial location of the spill and the nal desired location to which the spill must be moved. In this case, the robot or robots are told that the initial location is in the center of the front third of the room, and that the desired nal location of the spill is in the back center of the room, relative to the position of the entrance. The ultimate goal is to have the mission completed as quickly as possible without needlessly wasting energy.
For such a mission, it is quite possible that no individual robot possesses all the required capabilities. Thus, we must be able to custom-design a multi-robot team from the available pool of automata such that the group possesses all the required capabilities, and the robots contain a considerable amount of overlap in their abilities.
The challenge for each robot, then, is to select the appropriate action to pursue throughout the mission while responding appropriately to the e ect of its own actions, the actions of other team members, and dynamic changes in the environment or in the team itself.