@prefix vivo: . @prefix edm: . @prefix ns0: . @prefix dcterms: . @prefix skos: . vivo:departmentOrSchool "Applied Science, Faculty of"@en, "Mechanical Engineering, Department of"@en ; edm:dataProvider "DSpace"@en ; ns0:degreeCampus "UBCV"@en ; dcterms:creator "Maghsoud, Pegah"@en ; dcterms:issued "2014-09-10T14:17:46Z"@en, "2014"@en ; vivo:relatedDegree "Master of Applied Science - MASc"@en ; ns0:degreeGrantor "University of British Columbia"@en ; dcterms:description """This thesis investigates multi-robot cooperation in multi-robot systems (MRS) for simultaneous multi-object transportation in unknown, dynamic, and unstructured environments. Two distinct control frameworks are developed for MRS to achieve its global goal while resolving conflicts in the system. An autonomous and distributed algorithm that uses artificial immune system (AIS) is developed for multi-robot cooperation and it is validated using experimental work carried out on a team of real physical robots in the Industrial Automation Laboratory (IAL). Two deadlock handling approaches are considered to avoid shared resource conflicts in the system. One method prevents the system from getting into a deadlock situation and is so-called the prevention-based method. The other method autonomously detects the deadlocks and then recovers system from that situation, and is known as the detection-based method. Two separate deadlock resolution algorithms are developed for MRS; one based on the prevention method and the other based on the detection method. Either of these two deadlock handling algorithms is then combined with the multi-robot cooperation algorithm to generate two integrated task execution algorithms for the control frameworks of MRS. Feasibility and effectiveness of the developed control frameworks are demonstrated and evaluated through simulation of the MRS on the Webots simulation platform. Finally, using the simulation results, a comparative evaluation of the two control frameworks developed in this research is carried out with respect to task completion time, communication overhead, and the number of tasks executed."""@en ; edm:aggregatedCHO "https://circle.library.ubc.ca/rest/handle/2429/50337?expand=metadata"@en ; skos:note """AUTONOMOUS AND COOPERATIVE MULTI- ROBOT SYSTEM FOR MULTI-OBJECT TRANSPORTATION by Pegah Maghsoud B.A., The University of British Columbia, 2012 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE AND POSTDOCTORAL STUDIES (Mechanical Engineering) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) September 2014 © Pegah Maghsoud, 2014 ii Abstract This thesis investigates multi-robot cooperation in multi-robot systems (MRS) for simultaneous multi-object transportation in unknown, dynamic, and unstructured environments. Two distinct control frameworks are developed for MRS to achieve its global goal while resolving conflicts in the system. An autonomous and distributed algorithm that uses artificial immune system (AIS) is developed for multi-robot cooperation and it is validated using experimental work carried out on a team of real physical robots in the Industrial Automation Laboratory (IAL). Two deadlock handling approaches are considered to avoid shared resource conflicts in the system. One method prevents the system from getting into a deadlock situation and is so-called the prevention-based method. The other method autonomously detects the deadlocks and then recovers system from that situation, and is known as the detection-based method. Two separate deadlock resolution algorithms are developed for MRS; one based on the prevention method and the other based on the detection method. Either of these two deadlock handling algorithms is then combined with the multi-robot cooperation algorithm to generate two integrated task execution algorithms for the control frameworks of MRS. Feasibility and effectiveness of the developed control frameworks are demonstrated and evaluated through simulation of the MRS on the Webots simulation platform. Finally, using the simulation results, a comparative evaluation of the two control frameworks developed in this research is carried out with respect to task completion time, communication overhead, and the number of tasks executed. iii Preface This dissertation is an original intellectual property of the author, Pegah Maghsoud, working under supervision of Prof. Clarence W. de Silva. This work addresses multi-robot cooperation in multi-robot systems for multi-object transportation in unknown, dynamic, and unstructured environments. All of the work presented in this thesis was conducted at the Industrial Automation Laboratory, Department of Mechanical Engineering, the University of British Columbia, Vancouver campus. A version of Chapter 3 has been published in The 9th IEEE International Conference on Computer Science and Education, 2014. A version of the work and results presented in Chapter 5 will be submitted for publication. iv Table of Contents Abstract ................................................................................................................................... ii  Preface .................................................................................................................................... iii  Table of Contents .................................................................................................................. iv  List of Tables .......................................................................................................................... vi  List of Figures ....................................................................................................................... vii  List of Symbols ...................................................................................................................... ix  List of Abbreviations ............................................................................................................. xi  Acknowledgements ............................................................................................................... xii  Dedication ............................................................................................................................ xiii   Introduction ......................................................................................................... 1  Chapter 11.1   Research Objectives ................................................................................................ 2  1.2   Problem Definition .................................................................................................. 3  1.3   Related Work ........................................................................................................... 5  1.4   Contributions and Organization of the Thesis ......................................................... 9   Modeling of Artificial Immune System ............................................................. 13  Chapter 22.1   Biological Immune System ................................................................................... 13  2.2   Artificial Immune System (AIS) ........................................................................... 17  2.3   Modeling the Idiotypic Immune Network ............................................................. 18   Multi-Robot Cooperation Algorithm Using AIS ............................................... 21  Chapter 33.1   System Development ............................................................................................. 21  3.2   Idiotypic Immune Network and Multi-Robot Cooperation ................................... 24   v 3.3   Flowchart of the Developed Multi-Robot Cooperation Algorithm ....................... 28  3.4   Experimental Results ............................................................................................. 29   Resolving System Deadlocks in Distributed Systems ....................................... 31  Chapter 44.1   System Deadlocks ................................................................................................. 31  4.2   Methods for Handling Deadlocks ......................................................................... 32  4.3   Deadlock Prevention Method ................................................................................ 34  4.4   Deadlock Detection and Recovery Method .......................................................... 35   Deadlock Resolution in Multi-Robot Systems .................................................. 38  Chapter 55.1   Approach 1: Deadlock Prevention in Multi-Robot System .................................. 38  5.2   Approach 2: Including Deadlock Detection and Recovery into Multi-Robot Cooperation Algorithm ......................................................................................... 41  5.3   Simulation Results ................................................................................................. 46  5.4   Comparison of the Two Approaches ..................................................................... 57   Conclusion ......................................................................................................... 63  Chapter 66.1   Primary Contributions ........................................................................................... 63  6.2   Strengths and Limitations ...................................................................................... 64  6.3   Suggested Future Work ......................................................................................... 65  Bibliography ..........................................................................................................................67  Appendices .............................................................................................................................71   vi List of Tables Table 1 – Simulated Pioneer Robots. ............................................................................................ 47  Table 2 - Simulation Results of Prevention-Based MRS. ............................................................. 72  Table 3 - Prevention-Based System Runs for One Object. ........................................................... 73  Table 4 - Prevention-Based System Runs for Two Objects. ........................................................ 73  Table 5 - Prevention-Based System Runs for Three Objects. ...................................................... 74  Table 6 - Prevention-Based System Runs for Four Objects. ........................................................ 74  Table 7 - Simulation Results of Detection-Based MRS. .............................................................. 75  Table 8 - Detection-Based System Runs for One Object. ............................................................ 75  Table 9 – Detection-Based System Runs for Two Objects. .......................................................... 76  Table 10 – Detection-Based System Runs for Four Objects. ....................................................... 76  Table 11 – Detection-Based System Runs for Three Objects. ...................................................... 77   vii List of Figures Figure 1 - Schematic Diagram of the MRS. ................................................................................... 4  Figure 2 - Killer T-cells Activation Process. ................................................................................ 13  Figure 3 - B-Cell Activation. ........................................................................................................ 14  Figure 4 – Antibody Structure. ..................................................................................................... 15  Figure 5 - Antibody-Antigen Binding Mechanism. ...................................................................... 16  Figure 6 – Antibody Stimulation. ................................................................................................. 17  Figure 7 – (a) Antibody/Robot (b) Antigen/Task. ........................................................................ 23  Figure 8 – (a) Antibody/Robot (b) Antigen/Task. ........................................................................ 24  Figure 9 – Task Execution Algorithm. ......................................................................................... 28  Figure 10 – Experiment Results with Physical Robots. ................................................................ 29  Figure 11 – Prevention-Based Task Execution Algorithm for MRS. ........................................... 40  Figure 12 – Multi-Robot System in Deadlock State. .................................................................... 41  Figure 13 - Detection-Based Task Execution Algorithm for MRS. ............................................. 45  Figure 14 - Multi-Robot System Simulation Environment. .......................................................... 46  Figure 15 - Individual Attempts. ................................................................................................... 48  Figure 16 – Cooperative Attempts. ............................................................................................... 49  Figure 17 - Robots Leave the Object to Prevent System Deadlock. ............................................. 49  Figure 18 - Cooperative Object Transportation. ........................................................................... 50  Figure 19 - Unsuccessful Individual Attempt. .............................................................................. 51  Figure 20 – First Unsuccessful Cooperation Attempt. .................................................................. 51  Figure 21 – Second Unsuccessful Cooperation Attempt. ............................................................. 51   viii Figure 22 – Successful Cooperative Object Transportation. ........................................................ 52  Figure 23 – Robots Individual Attempts. ...................................................................................... 53  Figure 24 – Robots Cooperation Attempt. .................................................................................... 53  Figure 25 – System Stuck in a Deadlock Situation. ...................................................................... 54  Figure 26 – Deadlock Resolved. ................................................................................................... 54  Figure 27 – Cooperative Object Transportation. .......................................................................... 55  Figure 28 – Individual Attempt. .................................................................................................... 55  Figure 29 – First Cooperation Attempt. ........................................................................................ 56  Figure 30 – Transporting the Last Object. .................................................................................... 56  Figure 31 – The Effect of Coalition Sizes and Number of Objects on the Number of System Deadlocks. ..................................................................................................................................... 58  Figure 32 –The Effect of Number of Objects on Average Task Completion Time. .................... 59  Figure 33 –The Effect f Coalition Sizes on Average Task Completion Time. ............................. 60  Figure 34 – Communication Burden Due to the Number of Objects in the Task. ....................... 61  Figure 35 – Communication Burden Due to the Coalition Sizes. ................................................. 61  Figure 36 – Effect of Number of Robots on Task Completion Time. .......................................... 78  Figure 37 – Effect of Number of Robots on Task Completion Time. .......................................... 78  Figure 38 – Real Simulated P3DX and P3AT. ............................................................................. 79  Figure 39 - Simulated P3DX and P3AT. ...................................................................................... 79   ix List of Symbols 𝑥? Antibody 𝑦? Antigen ℱ Matching function 𝐶 Rate of change in concentration of antibody or antigen N Number of antibodies in the system M Number of antigen in the system 𝑘? Constant representing inequalities between antibody stimulation and suppression 𝑘? Constant representing the damping factor 𝑏 Rate constant that simulates the number of collisions per unit time 𝑝? Paratope of the initiating robot 𝑒 Antigen’s epitope 𝑖 Antibody’s idiotope 𝑝? Paratope chain of a robot pj Process j Ri Robot i Tj Task j 𝑟? Resource types 𝑤? Number of resources of each type 𝑃 Number of allocated resource to each task Tj Task i 𝑝™ Number of resources of type i allocated to task j x 𝑄 Number of resources of each type requested by each task but not yet allocated 𝑞™ Number of resources of type j requested by task i but not yet allocated to it 𝑉 Vector representing the number of available resources 𝑐? Cost of preempting resource 𝑟? 𝑔 𝑞™ − 𝑣? Function representing cost of preempting resource 𝑟? from task Ti xi List of Abbreviations AIN Artificial Immune Network AIS Artificial Immune System APC Antigen Presenting Cell AS Ant System BLE Broadcast of Local Eligibility CH Constant Heavy Chain CL Constant Light Chain DEC Discrete Event Controller IA Instantaneous Assignment IAL Industrial Automation Laboratory MR Multi-Robot MRS Multi-Robot System MRTA Multi-Robot Task Allocation MT Multi-Task SR Single-Robot ST Single-Task TA Time-Extended Assignment TCP/IP Transmission Control Protocol/Internet Protocol VH Variable Heavy Chain VL Variable Light Chain xii Acknowledgements First and for most, I offer my enduring gratitude to my supervisor Prof. Clarence W. de Silva who has inspired me throughout my graduate studies. Without his supervision, guidance, and support I would not have been able to accomplish this research project. It was a great honor for me to work with him and through his mentorship I have learned a wealth of lifetime lessons to take with me. I would also like to express my sincere thanks to my research committee members, Prof. Farrokh Sassani and Prof. Steve Feng, for their carful assessments and thoughtful feedbacks on my thesis. My special thanks goes to our former Lab Manager Dr. Muhammad Tahir Khan who has not only guided me through the research but has been a great mentor to me since I started working on this project as a volunteer student at IAL. I would also like to thank our current Lab Manager Dr. Roland H. Lang and my other colleagues at IAL who have helped me in this work; particularly, Shawn Yunfei Zhang and Edward Yanjun Wang. Finally, I wish to gratefully thank my family, specially my parents for their endless love and support throughout my life and for sacrificing a great deal to make all this possible for me. My deepest thanks go to my lovely sister Nika, who has always been there for me and for her love and support. xiii Dedication              I  ded icate   th i s   thes i s   to  my  be loved  parents  and  my  s i s t er   for   the i r  endless   love  and  pr i ce l e ss   sacr i f i c es .  Th is  work  would  not  have  been  poss ib le  w i thout   the i r   support . 1 Chapter 1Introduction Multi-robot systems (MRS) have become of great interest in the past decades and have been the subject of active research for years now. Instead of having a single powerful robot to execute a complex task, in an MRS, the task is decomposed into sub-tasks that are executed by a team of multiple robots, which through interaction with environment and cooperation with one another, accomplish an overall goal of the system. Multi-robot systems best serve in applications that are inherently distributed, cooperative, and complex. Distributed in the sense that the tasks arise at geographically different locations, at different times, and require different functionalities to be executed. Cooperative means more than one robot is needed to effectively carry out the task. Complex in the sense that the application is too extensive with multiple actions to be executed by a single robot or a centralized system and doing so would be time consuming and costly. If capable, MRS can benefit from asynchronous and simultaneous task executions, which could increase the overall speed of the system and could result in increased efficiency in the system. MRS are more robust and reliable as they benefit from the inherent redundancy of the agents in the system in the sense that failure of a robotic agent would not result in the failure of the entire system. Distributed systems are generally more scalable and have greater flexibility. Examples of their applications are search and rescue operations, automated homecare, planetary explorations, military operations, object transportation and payload deliveries. The problem of task allocation among robots has gained importance in recent years and is a key research topic in the field of MRS. Even more prominent is the challenge of allocating the 2 best-fit robot among the heterogeneous robots to increase the efficiency of the system. In cases where a robot team is in charge of executing one task at a time, no shared resource conflicts arise; however, if multiple tasks are executed simultaneously, then it is necessary to incorporate a conflict resolution policy into the resource allocation algorithm in order to avoid or resolve system conflicts and deadlocks. In the present work, a cooperative multi-robot system is developed for simultaneous multi-object transportation in an unknown, unstructured and dynamic environment. 1.1 Research Objectives The overall objective of the present research is to develop an autonomous and cooperative multi-robot system for multi-object transportation. In this pursuit, specific inspiration is gained from biological immune systems, for the use of artificial immune systems (AIS). In the proposed system framework, the primary objective is to develop an autonomous and fully distributed multi-robot cooperation algorithm that allows for simultaneous execution of multiple tasks in a multi-robot system. Once the algorithm is developed, a related objective of the thesis is to demonstrate the feasibility of the developed system through computer simulation and by experimenting using a team of real physical robots in our laboratory (Industrial Automation Laboratory—IAL). The secondary objective of the research is to increase the robustness of a multi-robot system by incorporating an autonomous conflict resolution algorithm within the developed primary algorithm of multi-robot cooperation, to avoid deadlocks in the system. Two separate conflict resolution algorithms are developed for MRS. One is based on deadlock prevention and the other one is based on deadlock detection and recovery. Each 3 deadlock resolution algorithm is incorporated into the developed primary algorithm for multi-robot cooperation to generate two separate overall algorithms for task execution using the control framework of MRS. A subsequent objective is to validate the feasibility of each developed control framework through simulation using the Webots simulation platform and compare their performances with regard to such aspects as completion time, communication burden, and number of tasks completed. 1.2 Problem Definition This thesis develops and evaluates an MRS for cooperative multiple object transportation. The work is inspired by human biological immune system and uses an AIS model. The considered MRS comprises multiple heterogeneous robots that cooperatively transport multiple heterogeneous objects to a designated goal location. The system is autonomous and fully distributed. The robots work in an unknown, dynamic, and unstructured environment where they have to wander around for objects while avoiding static and dynamic obstacles. The robots communicate, coordinate and cooperate with each other to achieve a global goal while autonomously resolving conflicts in the system. For a robotic system, simultaneous multi-object transportation is a design requirement to reduce task completion time and increase system efficiency. The number of objects in each task is unknown to the system and objects are introduced into the system in a random manner in time and space. Objects might require a single robot for their transportation or might require multiple robots. But the number of robots required to transport each object is unknown to the system and has to be identified autonomously by the system itself. Objects introduced to the system may differ in their size and weight and may require the 4 executing robots to have different sensing and actuating capabilities to transport them. The specific types of object transportation that are considered in the present experiments are box pushing and box carrying. Robots equipped with bumpers would perform box pushing and robots equipped with grippers would carry out box carrying. The robots in the system are heterogeneous and have different sensing and actuating capabilities. Each robot is equipped with a unique set of sensors and actuators. The objects are identified through color stickers that are attached to them. The partial sensing and actuating capabilities of the robots that are required to transport an object are identified through color decoding of the stickers. Robots do not have a global view of the environment and all objects and obstacles are detected through local sensing by the robots. The inter-robot communication is wireless and uses the TCP/IP communication protocol. A schematic diagram of the MRS considered in the present work is shown in Figure 1. Figure 1 - Schematic Diagram of the MRS. 5 1.3 Related Work Many different approaches have been proposed for multi- robot cooperation and task allocation in MRS. Among them behavior-based methods, market-based approaches, methods based on swarm intelligence, and approaches that use artificial immune system (AIS) are widely discussed in the literature. Gerkey (2004) classified MRS as either comprising single-task (ST) or multi-task (MT) robots executing either single-robot (SR) or multi-robot (MR) tasks. MR tasks, also known as tightly coupled tasks, require more than one robot to be executed and thus some form of robotic coalition is needed for their execution. Gerkey also classified task allocation in MRS as being either instantaneous assignments (IA) or time-extended assignments (TA). In instantaneous task allocation, unlike TA, there is no planning for future allocation and tasks are introduced randomly to the system with no prior knowledge of it coming up. In an MRS where task assignment is instantaneous (IA), the system may employ iterated assignment or online assignment. If upon task detection, previously assigned robots cannot be reassigned, then what results is an instance of online assignment. Some relevant work in the literature is classified and presented next. 1.3.1 Multi-Robot Cooperation An example of a behavior-based system is ALLIANCE, which uses motivational behaviors to achieve a fault tolerant adaptive action selection based on the robot’s internal state, state of other robots in the system, and the robots’ environment (Parker, 1998). Using Gerkey’s terminology as given in his taxonomy (2004), ALLIANCE may be classified into ST-SR-IA-iterated (single-task robots, single-robot tasks, instantaneous assignment-iterated) group of the 6 MRS. Broadcast of local eligibility (BLE) is yet another behavior-based system, and was developed by Werger and Mataric (2000). BLE is based on the broadcasting of local task eligibility and selecting the robot with the best eligibility to execute the task. In this case, task allocation is done through the cross inhabitation of behaviors between robots. BLE is also an instance of ST-SR-IA-iterated. Another multi-robot task allocation (MRTA) architecture is the market-based approach. In this approach, the tasks are auctioned within the system and when the auctioneer gathers information about the team, it determines the winner and assigns the task to be executed by the winner. MURDOCH is an auction-based system based on the control net protocol (Gerkey, 2002). It benefits from distributed negotiation mechanisms; however, it still has elements of a centralized system as the auctioneer determines the winner. MURDOCH is an instance of ST-MR- IA-online class of MRSs. M+ is another decentralized auction-based system (Botelho & Alamin, 1999). M+ is an ST-SR-IA-iterated system based on the control net protocol. In M+, it is assumed that the tasks and the order in which they should be executed are known. This information is sent out to the robots at the start of the system. This limits the system to domains where these are known. ASyMTRe-D (Parker & Tang, 2007) is yet another market-based system. It combines a high-level auction-based task allocation mechanism with the previously developed low-level ASyMTRe-D coalition mechanism (Parker & Tang, 2006) resulting in a distributed MRS. ASyMTRe-D is an instance of ST-MR-IA-iterated MRS. A third class of MRTA mechanism is swarm intelligence, which is inspired by the behavior of insects. Swarm-based methods use an ant system (AS) algorithm. These approaches best suit applications in which the tasks are spread over a relatively large area and their execution requires repetitive activities. Swarm-type systems typically comprise teams of large number of 7 homogeneous robots. Kube and Bonabeau (2000) modeled the cooperative transport of ants and developed a decentralized AS-based MRS. Zhang et al. (2007) developed a hierarchical algorithm for their task execution algorithm. In an upper hierarchical layer, a self-reinforcement learning algorithm is incorporated to differentiate the initially identical robots into “specialists” for task execution. In a lower hierarchical layrer, a distributed AS-based task allocation algorithm is utilized to deal with task assignment. Both these systems belong to the class of ST-MR-IA-online assignment. 1.3.2 MRS Using AIS Artificial Immune System is another method for MRTA, which is inspired by human biological immune system. Gao and Wei (2005) proposed a self-determination method for multi-robot cooperation based on the immune system model in which agents interact with each other and with the environment to produce a strategy to destroy non-self agents. In such a system, proper stimulated agents are selected based on the stimulus values, and during the whole process, several agents cooperate to achieve their global goal. After eliminating the antigens by self-determined cooperation, the system memorizes the different properties of each antigen in the knowledge library for use in the second immune response. The task allocation algorithm that is proposed in the present thesis is limited to a homogeneous group of robots. The system is an instance of ST-MR-IA-online assignment. Gao and Wei (2006) proposed a new multi-robot task allocation algorithm for a multi-robot system that used an artificial immune network (AIN). In the present work, an event triggered task allocation mechanism is integrated into their task allocation algorithm to reallocate tasks to 8 realize dynamic task allocation in the system. Three different methods are developed in the thesis to implement autonomous cooperation among robots based on the committed/opportunistic attribute of the robots. The developed system belongs to the class of ST-MR-IA-iterated assignment. The limitation of this system is that it only considers different robot speeds as the heterogeneity of the robots. Khan and de Silva (2008, 2009) developed a self-regulated fault tolerant multi- robot cooperation system based on the principles of artificial immune system (AIS). In the approach, cooperation of the agents rely on the broadcast of capabilities and the cost functions of the robots in the system. The system is able to accommodate partial and full failure of a robot during communication and cooperation. Nevertheless, the system does not address simultaneous object transportation in the workspace. This system also belongs to the category of ST-MR-IA-online assignment. 1.3.3 Deadlock Resolution in MRS The following related work in the literature address deadlocks in multi-robot systems. Ballal et al. (2006) proposed a new approach for task allocation in cooperative multi-mission robot teams. The system utilizes a matrix-based discrete event controller (DEC) as the framework to combine together greedy dynamic resource assignment and deadlock avoidance. At the occurrence of each event, the greedy algorithm is first implemented to update the resource assignment based on the resource requirement matrix. Then the new resource allocation is accepted if it is compatible with a certain deadlock avoidance policy called MAXWIP. Their proposed system comprises heterogeneous robots and is an instance of ST-MR-IA-iterated assignment. 9 Xu et al. (2007) developed a decentralized and cooperative market-based multi-robot system. To resolve deadlocks in the system, a global monitoring machine is designed to frequently access a blackboard and monitor the status of the tasks. If a deadlocked task is recognized, the so-called harmonize strategy is carried out at the superior level of human-computer interaction to resolve the deadlock. Like previous work, this system is also classified as ST-MR-IA-iterated assignment. Gao and Luo (2008) designed an MRS based on the artificial immune network (AIN). A static task allocation algorithm is developed based on the principles of antigen stimulus and inter-antibody interactions. Self-reinforcement learning of the antigen stimulus is introduced to accommodate dynamic task assignment and to avoid deadlock situation in the system. The waiting time of the robots is used as another source of the reinforcement signals. As a robot’s waiting time passes the threshold time and gets larger, the antigen stimulus of robot for the task decreases to a point where the robot may choose other tasks. In this manner, deadlocks are avoided in the system. This work belongs to the category of ST-MR-IA-iterated assignment according to Gerkey’s classification (Gerkey, 2004). 1.4 Contributions and Organization of the Thesis In this thesis, two separate control frameworks, which are based on AIS, are developed and comparatively evaluated. They are intended for a multi-robot system to cooperatively transport multiple objects in an unknown, dynamic, and unstructured environment. The main contributions of this thesis are as follows: 10 • An autonomous multi-robot cooperation algorithm is developed for an MRS to execute multiple simultaneous tasks in the work environment. The multi-robot cooperation uses AIS and is based on Jerne’s idiotypic network theory. • The feasibility of the developed schema is demonstrated through implementing the developed algorithms on a team of real physical robots and carrying out experiments of cooperative and simultaneous transport of multiple objects in the work environment. • Two novel conflict resolution algorithms are developed to avoid/resolve deadlocks in an MRS. Each deadlock resolution algorithm is combined with the developed multi-robot cooperation algorithm to generate two separate task execution algorithms for the control framework of the MRS. • The feasibility of each of the developed control frameworks is validated by implementing each of the developed task execution algorithms on a simulated MRS for multi-object transportation in the Webots simulation platform. • Finally, using the simulation results, the two developed control frameworks are comparatively assessed with regard to task completion time, communication overhead, and number of completed tasks. The organization of the thesis is as follows: In Chapter 1, the background on MRS is presented followed by the objectives of the present research. Then the problem addressed in this thesis and the characteristics of the multi-robot system that is studied are stated. After the problem definition, some relevant existing work in the field of MRS is discussed. 11 In Chapter 2, first some background on human biological immune systems is given and then Jerne’s idiotypic network theory on dynamic behavior of immune system is presented. This is followed by an introduction to the concept of AIS. Finally, the chapter is concluded by presenting a model to estimate the idiotypic immune network, which is later used for developing the multi-robot cooperation algorithm. In chapter 3, the multi-robot cooperation algorithm that is based on AIS is developed for simultaneous multi-object transportation. First characteristics of the considered MRS and the pertaining assumptions are stated. Then, the development of the multi-robot cooperation algorithm based on Jerne’s idiotypic immune network is presented. After that, a flowchart of the task allocation algorithm is given. This is followed by implementing the algorithm on a team of real physical robots in IAL and carrying out experimentation. Subsequently, the experimental results are presented. Chapter 4 addresses deadlocks in a distributed multi-processing system like MRS. Initially the conditions for deadlock occurrence in the system are stated. Then, methods for avoiding deadlocks in a distributed system are discussed. Two of the deadlock resolution approaches – the prevention method and the detection & recovery method –are then explained in greater detail, as they are later used in the developed system. Chapter 5 begins with the development of the prevention-based deadlock resolution algorithm for MRS. Then the developed algorithm is combined with the multi-robot cooperation algorithm that is developed in Chapter 3 to generate the first control framework for an autonomous deadlock free MRS. Section 5.3.1 presents the simulation results of the feasibility verification of the so-called prevention-based control framework for MRS. The second section of the chapter lays out the development of the second deadlock resolution algorithm, which is based 12 on the deadlock detection and recovery method. Similar to the development of the first framework, the deadlock detection and recovery algorithm is incorporated into the cooperation algorithm that is developed in Chapter 3 to generate the second control framework for an autonomous conflict free MRS. The simulation results for feasibility verification of the so-called detection -based control framework for MRS is presented in section 5.3.2 of the chapter. Finally, based on the simulation results, the two control frameworks are compared, and the results are presented in section 5.4. Chapter 6 summarizes the contributions of the thesis and presents the conclusions obtained from the comparison results. Also, it presents some major strengths and limitations of the developed multi-robot systems. The chapter ends by stating suggestion for possible future work. 13 Chapter 2Modeling of Artificial Immune System 2.1 Biological Immune System An immune system is a system of biological structures and processes within an organism that protects against disease by identifying and killing pathogens and tumor cells. It detects a wide variety of agents, from viruses to parasitic worms, and distinguishes them from the body’s own healthy cells and tissues in order to function properly. The fundamental constituents of the immune system are lymphocytes. On the surface of each lymphatic cell are receptors that enable them to recognize foreign substances. There are two main types of lymphocytes: B-cells and T-cells. T-cells come in two different types, helper cells and killer cells. Helper T-cells are the major driving force and the main regulators of the immune defense. Their primary task is to activate B-cells and killer T-cells. However T-cells themselves have to be activated. Once an antigen is introduced into the body, the so-called Antigen Presenting Cell (APC) ‘eats’ the invader and presents information about the captured antigen by displaying an antigen fragment from the invader on its own surface. When the receptor of the helper T-cell recognizes the antigen, the T-cell is activated. This process is illustrated in figure 2. Figure 2 - Killer T-cells Activation Process. 14 Once the helper T-cells are activated, they start to produce proteins that activate the B-cells and the killer T-cells. A B-cell searches for an antigen matching its receptors and if it finds such an antigen it connects to it. But the B-cell triggering signal is still off. Now the helper T-cells help the B-cell to become fully activated. Once activated, the B-cells start to divide and create new cell types, plasma cells and memory cells. A plasma cell is specialized in producing a specific protein-called an antibody-that will respond to the same antigen that matched the B-cell receptor. The antibodies that are produced by the B-cells recognize non-self antigens and ambush them within the body’s blood stream. However, if they are unable to fight the antigen, they will coordinate with other antibodies to cooperatively destroy the existing antigen. The memory cells that are produced by a B-cell are responsible for “remembering” specific intruders so that the next time when the same intruder enters the blood stream, the immune system activates much faster. Figure 3 shows the activation of B-cells in response to antigen existence in the body. Figure 3 - B-Cell Activation. 15 2.1.1 Antigen Elimination by Immune System An antibody is a large Y-shaped protein that is used by the immune system to identify and neutralize antigens. Each tip of the “Y” of an antibody contains a paratope that is specific for one particular epitope on an antigen. In such a structure, a paratope is analogous to a lock and an epitope is analogous to a key. They can bind together with precision. An antibody consists of two chains, called light chain and heavy chain. The light and heavy chains are each divided into two sections, variable and constant, as illustrated in Figure 4. The variable region serves as an antigen-binding site and is called a paratope. There are several different types of antibody heavy chains (resulting in different types of antibodies). They are grouped into different isotypes and help direct the appropriate immune response for each different type of a foreign invader. Figure 4 – Antibody Structure. As mentioned, once an antigen intrudes the human body, B-cells are activated and they start producing an antibody whose paratope is complementary to the epitope of the antigen. These antibodies will then attach to the antigen and try to eliminate it. However, if they are unable to do 16 so, they coordinate with other antibodies and cooperatively destroy the invader. Figure 5 represents the antibody-antigen binding. When an antibody recognizes an antigen, the paratope of and the epitope bind together with certain strength proportional to the binding affinity between them. A paratope may not be an exact match of the epitope and this results in a week binding affinity, in which case there is less possibility of killing the antigen. The recognition of an antigen will stimulate the proliferation and differentiation of the immune cells that produce matching clones or antibodies specific to the antigen. This process is called clonal expansion. Figure 5 - Antibody-Antigen Binding Mechanism. 2.1.2 Idiotypic Network Theory In 1974, N. K. Jerne suggested that the immune system has a dynamic behavior, and the immune cells also recognize each other even in the absence of external stimuli. For this, he formulated the Idiotypic Network Theory, which is based on the fact that in addition to paratope, an antibody also possesses a set of epitopes. Consequently they are recognizable by other antibodies. The epitopes that are unique to an antibody type are termed idiotopes. The network 17 theory implies that B-cells are not isolated, rather they communicate with each other via dynamic network interaction. When idiotope of an antibody or epitope of an antigen is recognized by paratope of the antibody, the antibody is stimulated. However, if idiotope of the antibody is recognized by paratope of another antibody, the antibody is suppressed. Immune system balances diversity and removes useless antibodies in the system and this is modeled as suppression in Jerne’s Idiotypic Network Theory. As Figure 6 illustrates, in the following immune network, the Antigen stimulates both Antibody 1 and 2. Also it indicates that Antibody 2 is stimulated by Antibody 3 while, Antibody 3 is suppressed by Antibody 2. Figure 6 – Antibody Stimulation. 2.2 Artificial Immune System (AIS) Artificial immune systems are adaptive systems that simulate a biological immune system and uses theoretical immunology and immune principles. In the present work, an AIS is established upon the idiotypic network theory developed by Jerne. It is a distributed autonomous system in which multiple agents cooperatively perform a common task. 18 Key properties of an AIS are listed below: • Distributed: The system is distributed. Unlike a centralized system where it is necessary to have a supervisory computer to allocate the tasks and to control the agents in the system, in a distributed system, each agent has its own controller in which each computer executes its own activities while the system behaves in harmony as a whole. • Autonomous: Agents have the unique capability to determine responses to achieve common tasks through independent decision-making and communication. • Dynamic Network Interaction: In order to cooperate with each other, B-cells in the immune system communicate with each other via collective dynamic interaction. • Self-non-self Recognition: Through pattern recognition, B-cells and T-cells are capable of differentiating self and non-self agents that are introduced into the body. Furthermore, if the pattern corresponds to a non-self agent, depending on the pattern that is recognized, they will take proper action to ambush it. • Property Recognition: In the immune system, antibodies of B-cells are capable of recognizing the features of the antigens that they find and the properties of the other antibodies as well in the system with which they interact. 2.3 Modeling the Idiotypic Immune Network In 1986 Farmer et al. formulated the idiotypic network theory for computer simulation. In their work, the rate of proliferation of antibodies is modeled by a differential equation representing the antibody’s stimulation and suppression in response to antigens and other antibodies in the system. 19 In this model, each antibody is represented as a pair of strings, one denoting the paratope and the other indicating the epitope or the so-called idiotope of the antibody. Each antigen is also represented with a string illustrating its epitope. The degree of match between a paratope and an epitope/idiotope mimics the biding affinity between the two agents. To evaluate the binding affinity, the antibody’s paratope string is compared with the antigen’s epitope string. If the degree of match equates or exceeds the threshold value S, the antibody is considered to be stimulated. The strength of the binding affinity ℱ is a function of the number of matches between paratope and epitope strings. The developed model proposes that in a system with N antibodies 𝑥?, 𝑥?,… , 𝑥? and M antigens 𝑦?, 𝑦?,… , 𝑦? , the rate of change in concentration C of antibody 𝑥? is governed by the differential equation: 𝐶 𝑥? =  𝑏 ℱ™ 𝐶 𝑥????? 𝐶 𝑦? + ℱ™ 𝐶 𝑥????? 𝐶 𝑥? − 𝑘? ℱ™ 𝐶 𝑥????? 𝐶 𝑥? − 𝑘?𝐶 𝑥? (2.1) The first summation in the brackets - ℱ™ 𝐶 𝑥????? 𝐶 𝑦? - represents the stimulation of antibody 𝑥? in response to all antigens 𝑦?  in the system. ℱ™ is the matching function that represents the degree of the binding affinity between antibodies and antigens. The term 𝐶 𝑥? 𝐶 𝑦? expresses the probability of collision/stimulation between antibodies and antigens. The second sum - ℱ™ 𝐶 𝑥????? 𝐶 𝑥? - represents the stimulation of antibody 𝑥? in response to all antibodies 𝑥?. In this term, ℱ™ denotes the degree of recognition for stimulation. The term 𝐶 𝑥? 𝐶 𝑥? models collisions among the antibodies. The third term in the brackets - 𝑘? ℱ™ 𝐶 𝑥????? 𝐶 𝑥? – is responsible for the suppression in the system. In this term, ℱ™ models the degree of recognition for suppression and 𝐶 𝑥? 𝐶 𝑥? 20 is the collision factor. Also, k? is a constant that allows possible inequalities between antibody stimulation and suppression. If k? = 1 these forces are equal. In equation (2.1), variable b is a rate constant that simulates the number of collisions per unit time. The last term - k?C x? - denotes the tendency of the antibodies to die out in the absence of interaction. In this expression, k? is a constant representing the damping factor. The artificial immune network presented in this chapter is used in the next chapter to develop an algorithm for the cooperation of robots in a multi-robot system for simultaneous object transportation in a work environment. 21 Chapter 3Multi-Robot Cooperation Algorithm Using AIS 3.1 System Development In the first part of this chapter, a multi-robot system that uses AIS is developed to address the challenges of simultaneous cooperative task execution. Similar to a biological immune system, MRS is composed of multiple autonomous robots that make independent decisions while cooperating with each other to execute a common task. The coordination among the robots uses the principles of Jerne’s idiotypic network theory as presented in the previous chapter. Robots in a multi-robot system resemble antibodies in the immune system. Each robot has its unique capabilities and properties, which are represented in a chain-like configuration corresponding to a paratope in an AIS. Similarly each task in the multi-robot system corresponds to an antigen in a biological immune system. Task properties and the required capabilities for the task execution are also represented in a chain configuration similar to the epitope string in an AIS. A binding affinity function is developed to resolve the conflicts among the robots and to assure that the most suitable robots are chosen to cooperate in the task execution. 3.1.1 Assumptions In developing a framework for multi-robot cooperation that uses an AIS, some assumptions are made to properly characterize the work. These assumptions are as follows: • The robots in the system are heterogeneous. In other words, each robot has its own properties and its own unique set of sensing and actuating capabilities. 22 • The framework is developed for object transportation in an unknown, dynamic, and unstructured environment comprising of static and dynamic obstacles. • The workspace is comprised of both single-robot objects and multi-robot objects. • The objects are heterogeneous and color-coded. Each object has a unique set of properties and certain required abilities for transportation. Partial required capabilities, physical parameters, and the global position of these objects are identifiable through color decoding. • Robots do not have a global view of the system and the environment. All the sensing is local. • Each robot makes independent decisions but is capable of coordinating and communicating with other robots in the system. • The system is fully distributed; therefore, there is neither a central supervisor to control the robots nor a central database for the robots to access global information. 3.1.2 Multi-Robot System and Immune System In the present work, the structural framework of the multi-robot system is founded upon the principles of AIS. In such a system, each robot is analogous to an antibody and the robot capabilities correspond to paratopes. Furthermore, in the case of cooperative task execution, the required capabilities that are sent from the initiating robot to other robots are analogous to idiotopes of antibodies. The job of object transportation is analogous to an antigen and correspondingly the properties of the task are analogous to the epitopes of the antigens. 23 Figure 7 represents the mapping of MRS onto an immune system. Figure 7 – (a) Antibody/Robot (b) Antigen/Task. As stated in section 2.1.1 of Chapter 2, an antibody consists of two light chains and two heavy chains. The upper part of the light and heavy chains forms a variable region, which serves as the antigen’s binding site called paratope. The constant light chain CL represents the sensory data including obstacle existence, and the robot’s position, velocity, and orientation. The constant heavy chain CH stores the communication data such as the IP addresses, the degree of binding affinity known as the cost value, coordinates of the object, and the required capabilities if help is needed. The variable region or the paratope is also divided into a variable light chain VL and a variable heavy chain VH. VL denotes the state of the robot, which for example might be Wander, Wait, or Stimulate. The variable heavy VH chain represents the capabilities of the robot, which include the payload capacity, push/lift capabilities, and whether it is equipped with a camera, bumpers, and sonar sensors. Next, the idiotope of an antibody is responsible for inter-antibody stimulation (multi-robot coordination). It represents the required capabilities that the assisting robot should possess if it is to help the initiating robot. 24 The epitope of an antigen (task) represents the capabilities that are required to transport the object. This is indicated in figure 8. Figure 8 – (a) Antibody/Robot (b) Antigen/Task. 3.2 Idiotypic Immune Network and Multi-Robot Cooperation The idiotypic immune network developed by Jerne suggested that both antigens and other antibodies could stimulate an antibody. When an antigen (task) stimulates an antibody (robot), the antibody compares the epitope of the antigen with its own paratope. If the degree of matching between them is strong, the antibody starts to proliferate and destroy the antigen (execute the task/transport the object) itself. However, if the degree of matching is weak, the antibody starts to stimulate other antibodies to cooperatively ambush the antigen. At this stage, the antibody compares its own idiotope with the paratope of the other antibodies and if the degree of matching is strong, it stimulates these antibodies. Among the stimulated antibodies, the one with the highest binding affinity is selected to cooperate with the initiating antibody, and all the other stimulated antibodies will be suppressed. 25 Similar to the idiotypic network that was formulated by Farmer et al., the multi-robot cooperation can be represented by the following formula. 𝑥 = ℱ™ 𝑥?𝑦? + ℱ™ 𝑥?𝑥????? − 𝐺™ 𝑥?𝑥????? (3.1) The first term of equation (3.1) - ℱ™ 𝑥?𝑦? - represents stimulation of an antibody by an antigen. In the framework of multi-robot system this term represents object detection by a robot. Once an object (antigen) is detected, the object properties and the required capabilities 𝑦? (epitope) are compared with the robot capabilities 𝑥? (paratope). Here ℱ™ is the matching function for finding the degree of matching between epitope and paratope. The second term of equation (3.1) - ℱ™ 𝑥?𝑥????? - represents the stimulation of other antibodies by the initiating antibody. In other words, when the initiating robot 𝑥? (antibody) is not capable of executing the task on its own, it sends a help signal to all the other robots in the wandering state 𝑥? (stimulated antibodies). In the help signal, the initiating robot sends the required capabilities (idiotope) that the assisting robot should have for cooperation. Also, ℱ™ is the function that matches the idiotope of the initiating robot with the paratope of the other free robots. In other words, it compares the required capabilities with the capabilities of the other robots. The last term of equation (3.1)- 𝐺™ 𝑥?𝑥????? - denotes suppression of the stimulated antibodies. Among the robots that possess the required capabilities 𝑥? to cooperate with initiating robot 𝑥?, the most suitable robot is chosen to help. To select the most suitable robot, 𝐺™ compares the costs (binding affinity) of the robots that are eligible and for cooperation picks the robot with the lowest cost. 26 Besides the required capabilities, the help signal sent by the initiating robot contains information about the coordinates of the detected object. For the purpose of the present research, the cost is a function of the distance to the object and the distance is measured giving the robots own position and the position of the object. Embedded encoders in the robot give the global position of the robot at each instance. As denoted in the assumptions of section 3.1.1, the global position of the object is assumed to be known and identifiable through color decoding. In the following sections the matching functions between epitope and paratope, and idiotope and paratope are modeled. 3.2.1 Matching Function Between Antibody and Antigen As discussed in section 3.1.2, robot capabilities are represented as a chain of properties similar to the antibody’s paratope. Denoting by“𝑝?” the paratope of the initiating robot, let 𝑝? = 𝑏𝑢𝑚𝑝𝑒𝑟, 𝑐𝑎𝑚𝑒𝑟𝑎, 𝑝𝑢𝑠ℎ The required capabilities and properties of the object are given as a chain similar to the antigen epitope: 𝑒 = 𝑏𝑢𝑚𝑝𝑒𝑟, 𝑝𝑢𝑠ℎ Once a robot detects an object, it compares its own paratope with the epitope of the object. If it has all the required capabilities, it will attempt to transport the object on its own. If the robot’s attempt becomes unsuccessful, it will record the object’s required capabilities on the robot idiotope "𝑖" and will send out a help signal. The idiotope indicates the capabilities that the assisting robot should possess to be eligible for cooperation. 𝑖 = e =   𝑏𝑢𝑚𝑝𝑒𝑟, 𝑝𝑢𝑠ℎ 27 3.2.2 Matching Function for Stimulation Degree of Recognition After the initiating robot broadcasts the help signal that carries information about the required capabilities (idiotope, i), other robots in the wandering state compare their capabilities (paratope, 𝑝?) with idiotope i. If the idiotope and the paratope match, the antibody is stimulated. Denoting by 𝑝? the paratope chain of a robot in the wandering state that receives the help signal, let 𝑝? = 𝑝𝑢𝑠ℎ, 𝑏𝑢𝑚𝑝𝑒𝑟, 𝑐𝑎𝑚𝑒𝑟𝑎 If the antibody’s (robot’s) paratope chain 𝑝? has all the required capabilities in the initiating antibody’s (robot’s) idiotope, the antibody is stimulated and is qualified to help. 3.2.3 Matching Function for Suppression Degree of Recognition Among all the stimulated antibodies (qualified robots), the most suitable one is chosen to help in the task, and the rest are suppressed. The most suitable robot is the one with the minimum cost. The cost of each robot is inversely proportional to the distance of the robot to the object. Once it is determined which robot will cooperate, the other stimulated robots will return to the wandering state and will search for other objects. 28 3.3 Flowchart of the Developed Multi-Robot Cooperation Algorithm The task execution algorithm for multi-robot cooperation that is developed in the present work is shown in the flowchart of figure 9. Figure 9 – Task Execution Algorithm. 29 3.4 Experimental Results To demonstrate the feasibility of the developed multi-robot cooperation algorithm, the multi-robot system is implemented and experimented on a team of real physical robots in our laboratory. The team is comprised of two pioneer P3DXs and a P3AT robots. Boxes shown in figure 10a are the objects that have to be detected and transported. It is assumed that the robots would identify some of the properties and partially required capabilities of each object through decoding the colored stickers attached to the objects. Although the technology for a robot to autonomously identify properties like the object pose and size exists, the focus of the present work is on task allocation; therefore, less emphasis is given to identifying object properties. Instead it is assumed that such information would be readily available to the robot upon object detection. The experimental results are presented in figure 10. (a) –Wander in the environment (b) – Concurrent individual attempts (c) – Cooperative attempt (d) – All boxes are transported Figure 10 – Experiment Results with Physical Robots. 30 In figure 10a, the robots start to wander about in the workspace. While wandering, the robots search for objects and avoid obstacles in the work environment. Each of robots 1 and 2 detects an object and approaches that object to attempt pushing it individually, as shown in figure 10b. Before approaching the boxes however, each robot first checks if it has the partial required capabilities to transport the box. For the purpose of this experiment the designated goal location is set to be the far end of the workspace. As figure 10c illustrates, robot 1 is successful in individually pushing the box to the goal location while robot 2 is unsuccessful in its individual attempt and has asked for a cooperating robot to help. Since robot 3 is available in the system and has the partial required capabilities to help robot 2, it will respond to the request of robot 2’ and will approach box 2 for cooperation. Then, robots 2 and 3 cooperatively push box 2 to the goal location and return to the wandering state to search for more objects in the environment, as illustrated in figure 10d. Through experimental results, it was observed that as the number of objects in the environment increased, the system faced shared resource conflicts (i.e., deadlocks) a number of times; therefore, the number of times the system failed to accomplish its task increased correspondingly. It was also observed that the number of deadlocks increased as the number of robots required to cooperate in each task increased. When the system would fall into a deadlock state, the system had to be restarted. This would lower the efficiency of the system. Therefore, to avoid system failures due to system deadlocks, two deadlock resolution algorithms are developed and incorporated into the multi-robot cooperation algorithm developed in this chapter. This would allow the multi-robot system to autonomously detect and resolve conflicts in the system effectively, without having to restart the system. 31 Chapter 4Resolving System Deadlocks in Distributed Systems 4.1 System Deadlocks A recent challenge in the development of fully distributed MRS has been the efficient utilization of system resources by properly distributing them among concurrent tasks. In any system of this type, conflicts in the usage of shared resources can arise. They must be addressed and resolved. In particular, system deadlocks should be avoided or resolved. If the timing resource requests by different tasks results in a state that two tasks wait for the resources acquired by one another to complete the tasks, neither of the task could be carried out, and hence system operation could not proceed further. Then, the system is said to be in a deadlock. As a simplified example, assume that there are two processes p1 and p2 and there are two resources R1 and R2. Suppose that p1 has acquired R1 and also needs R2 to accomplish its task. Simultaneously, p2, has acquired R2 and requires R1 to complete its task. Then, both p1 and p2 have to wait for a resource that is needed by the other. In this situation there is a mutual dependency between the two processes and neither of them can proceed to execute its task. In such case if a proper deadlock resolution policy is not incorporated into the system, processes have to be restarted. In a system with possible deadlocks a concurrency control algorithm is required to handle them. As is the case with many other aspects of a distributed system, deadlock handling is more difficult because there is no central agent to manage resource allocations and each agent has to have its own “local” concurrency control. 32 For a deadlock situation to arise, all the following conditions must exist in a system (Coffman JR. et al., 1971): A. There exist resources that can only be used by one task at any one time – “Mutual Exclusion.” B. Until a task is completed, its acquired resources cannot be forcibly removed from it – “No Preemption.” C. Resources are requested in a circular sequence such that process pi is waiting for a resource held by pj which is in turn waiting for a resource held by pi. – “Circular Wait.” D. Tasks hold on to the acquired resources while waiting for the required additional resources – “Hold and Wait.” If all these conditions co-exist, the system is in a deadlock situation. 4.2 Methods for Handling Deadlocks Next, four existing approaches for resolving deadlocks are discussed. 4.2.1 Ignorance This is the simplest approach and is common in applications where the probability of deadlock occurrences is low. When a deadlock occurs, the system is rebooted and starts over from the initiating state. 4.2.2 Avoidance Deadlock avoidance algorithms are applicable if some advance information on resource requests is available. With this approach, deadlocks may occur, but there are resource allocation algorithms to avoid them. 33 In 1968, Dijkstra came up with the Banker’s Algorithm to avoid system deadlocks. In this algorithm the resource request would be denied even if that resource is free, if granting the resource could potentially result in a deadlock at some time in the future. The system always maintains itself in a so-called “safe state.” Then, at any one time there are sufficient free resources left in the system so that each process can acquire all the required resources in a special sequence to complete its task. Furthermore, when a task is completed, the acquired resources are released so that other processes can use them and proceed with their task executions (Dijkstra, 1968). 4.2.3 Prevention For the cases where no advance information on resource requests is available, one or more of the four necessary deadlock occurrence conditions discussed in section 4.1 can be removed in order to prevent deadlocks. This approach is discussed in detail in section 4.3. 4.2.4 Detection and Recovery In this approach, unlike the avoidance and prevention methods, deadlocks may occur in the system but there are detection and recovery algorithms that are incorporated to resolve them. This approach is discussed in detail in section 4.4. In conclusion, among the stated four approaches, the approaches of deadlock “prevention” and “detection and recovery” are considered for incorporation into the multi-robot cooperation algorithm developed in the present thesis. Although “Ignorance” is the simplest approach of deadlock resolution, it is only practical when there is low possibility of deadlock occurrence in the system. Typically, this not the case in a distributed MRS as developed in the present work. “Avoidance” approaches are suitable if advance information on resource usage is available. In 34 the proposed multi-robot system, it is assumed that tasks are introduced into the system randomly and there is no a-priori knowledge on the type and number of resources required for execution of each task. Therefore, the “avoidance” method would not be applicable to the proposed system. 4.3 Deadlock Prevention Method Deadlocks could be prevented if a least one of the following four necessary deadlock conditions is removed: A. Mutual Exclusion Mutual Exclusions can only be denied if resources are sharable as when multiple processes can acquire a resource at the same time. For instance, in an MRS where resources are the robots in the system and sharing of the resources is not possible, mutual exclusion removal is not applicable. B. No Preemption To remove the No Preemption condition, it must be possible to take away resources acquired by a process and to give them to other waiting processes. If a process is holding some resources and requests a resource that cannot be granted to it, it has to release all its acquired resources to prevent possible deadlocks. This approach; however, has a high cost of preemption because tasks might be preempted even when there is no deadlock. C. Circular Wait Resources are granted in a special order to prevent Circular Wait. However, imposition of linear ordering of resources only applies to static allocation of resources, which in turn reduces concurrency in the system. 35 D. Hold and Wait To remove the Hold and Wait condition, each process must request all of its required resources at once and should only proceed when it has acquired them all. This method is not applicable to systems where the number of required resources is not initially known. Furthermore, removing the Hold and Wait condition may cause starvation in the system. Starvation happens when a process is indefinitely postponed because its required resources are not allocated to it and are given to another process, although those resources are available in the system. In summary, one or more of the listed conditions could be removed to prevent deadlocks in a system. However, removal of each of these four conditions has its own requirements and limitations. For instance, removal of Mutual Exclusion is limited to systems where resources are sharable or removal while Circular Wait or Hold and Wait is only applicable if a-priori knowledge of system resource usage is available to the system. Furthermore, in the latter two approaches, resource allocation has to be done off line and this reduces system concurrency and drops the efficiency. Removal of the No Preemption condition is limited to systems where tasks can be preempted and the state of the system can be saved and restored later. 4.4 Deadlock Detection and Recovery Method Another approach to deadlock resolution is deadlock detection and recovery where an algorithm is incorporated into the system to automatically detect and recover from the deadlock state. In 1971, Coffman came up with an algorithm to detect deadlocks in a system comprising more than one resource of a type (Coffman, 1971). 36 In Coffman’ approach, 𝑟?  represents the resource types and 𝑤? represents the number of resources of each type. Matrix 𝑷 represents the number of allocated resources to each task 𝑇?; therefore, element 𝑝™ represents the number of the resources of type 𝑗 that are allocated to 𝑇?. Matrix 𝑸 represents the number of resources of each type being requested by 𝑇?  that are not yet allocated to it. At any time the number of available resources is presented by vector 𝑽: 𝑣? = 𝑤? − 𝑝™???? (4.1) Assuming that at any time instant (t), 𝑽 is given and the matrices 𝑷 and 𝑸 are available, the following algorithm as presented by Coffman may be used to detect deadlocks in the system. 4.4.1 Coffman’s Deadlock Detection Algorithm • Step 1: Initialize the number of resources of each type 𝑊 with the number of resources of each type available 𝑉 𝑡 . • Step 2: Mark all the tasks that have not been allocated any resources yet. In other words, mark rows in the P matrix in which all the row elements are zeroes. Leave the rest unmarked. • Step 3: Search among the unmarked rows; if there exists a row 𝑖 for which 𝑄? 𝑡 ≤𝑊, move to step 4. Otherwise, terminate the algorithm and go to step 5. • Step 4: For the  𝑖?? row in step 3, add the number of resources allocated (𝑝? 𝑡 ) to 𝑊 and return to step 3. Mark the 𝑖?? row. 𝑊 + 𝑝? 𝑡 →  𝑊 • Step 5: System would be in a deadlock, if and only if upon termination, there remain unmarked rows. 37 4.4.2 Coffman’s Deadlock Recovery Algorithm Once a deadlock is detected, a mechanism is required to recover the system from the deadlock. One solution for this is to abort the deadlocked tasks in a special sequence until sufficient resources are released so that the blocked tasks can deploy them and proceed with their execution. Coffman suggested to release resources in an ascending order of task sizes, and came up with the following cost function to represent the cost of taking back resources from a task 𝑇? (Coffman, 1971): 𝑐????? . 𝑔 𝑞™ − 𝑣? 𝑤ℎ𝑒𝑟𝑒  𝑓𝑜𝑟  𝑞™ > 𝑣?:    𝑔 𝑞™ − 𝑣? = 𝑞™ − 𝑣?   𝑎𝑛𝑑  𝑓𝑜𝑟    𝑞™ ≤ 𝑣?:    𝑔 𝑞™ − 𝑣? = 0 (4.2) In equation (4.2), 𝑐? is a fixed cost of taking back a resource of type 𝑟? from task 𝑇?. If for any resource 𝑟?, 𝑞™ > 𝑣? it illustrates that this resource is not currently available in the system and hence preempting it would add to the total preemption cost of 𝑇?. In the approach proposed in the present thesis, tasks are aborted in the ascending order of preemption costs until the system is out of the deadlock state. To summarize, in this chapter, four existing approaches to handle system deadlocks were discussed. Out of the four methods, two approaches were chosen - deadlock prevention and deadlock detection and recovery - that best suited for incorporation into the multi-robot cooperation algorithm of the present work. These two approaches were discussed in detail. In the next chapter, each of these two approaches is incorporated into the multi-robot cooperation algorithm developed in chapter 3 to generate two separate control frameworks for an MRS. 38 Chapter 5Deadlock Resolution in Multi-Robot Systems To resolve deadlocks in the multi-robot cooperation algorithm as presented in the thesis, two approaches are developed and incorporated. In the first approach, the deadlock prevention method prevents the system from getting into a deadlock situation. In the second approach, the deadlock detection and recovery method detects a deadlock and autonomously recovers from it. The overall cooperative task execution algorithms are developed by incorporating the two deadlock resolution algorithms. Next, to evaluate the performance, the developed multi-robot systems are simulated on the Webots simulation platform. Lastly, in this chapter, the overall performance of the two deadlock handling approaches is comparatively assessed. 5.1 Approach 1: Deadlock Prevention in Multi-Robot System As elaborated in chapter 4, system deadlocks can be prevented if at least one of the four necessary deadlock conditions is removed. The four conditions are Mutual Exclusion, No Preemption, Circular Wait, and Hold & Wait. For the multi-robot system that is developed in the present thesis, the only applicable approach to prevent the system deadlocks is the removal of the No Preemption condition and thereby letting the system to forcibly take back the acquired resources from a task when necessary. In an MRS, the resources are the robotic capabilities (camera, bumper, gripper, etc.), which are not sharable. Hence, removal of the Mutual Exclusion does not apply. As discussed before, in order to avoid Circular Wait and Hold &Wait situation, an advance model of resource allocation is required and the resource allocation has to be done statically. In contrast, in the multi-robot system that is developed in the present work, tasks are 39 randomly introduced into the system and the resource allocation is dynamic. Therefore, removing the Circular Wait and Hold & Wait condition from the system does not apply to the developed multi-robot system. 5.1.1 Incorporating Prevention Method into the Cooperation Algorithm In the multi-robot cooperation algorithm that is developed in chapter 3, system deadlocks are not addressed. If the system gets into deadlock state, it has to be restarted manually. If an initiating robot signals for additional help but no robot with the required capabilities is available to help, the initiating robot will continue broadcasting the help signal regardless of the possibility of the system being in a deadlock state. With the proposed deadlock prevention algorithm, however, if a robot with the required capabilities is not available in the system, the initiating robot and its other cooperating robots leave their task and return to the wandering state. Then, if there is a circular wait in the system, the second task that is holding on to the requested resources and is waiting for the released resources, will acquire the released resources and will continue with the task execution. In this manner, the system is prevented from getting into a deadlock state. A drawback of this approach, however, is that resources might be released even when there is no mutual wait for the resources and the system is not in a deadlock state. 40 5.1.2 Prevention-Based Control Framework for MRS – Approach 1 This prevention-based algorithm is combined with the multi-robot cooperation algorithm and the overall control framework for MRS task execution is developed. This scheme is presented in the flowchart of figure 11. Figure 11 – Prevention-Based Task Execution Algorithm for MRS. 41 5.2 Approach 2: Including Deadlock Detection and Recovery into Multi-Robot Cooperation Algorithm Deadlock is defined as the state in the system where tasks mutually wait for the resources acquired by one another. In other words, a circular wait exists between tasks that wait to acquire their resources. Figure 12 illustrates a sample deadlock situation in an MRS. In the shown scenario, robot 2 and 3, which are correspondingly the initiating robots to handle object 1and 2 – both have broadcasted help signals and are in the wait state. A robot is said to be in the wait state, when it sends help signal but it does not receive any help because there is no robot with the required capabilities available in the system. In the shown scenario both robot 2 and 3 are waiting for a robot with bumper to become free to cooperate with them. However, since they are mutually waiting for the resource acquired by one another, the system is essentially in a deadlock. Notice that robot 1 is free but because it does not have a bumper, it is unable to help either of the initiating robots to push the boxes. Figure 12 – Multi-Robot System in Deadlock State. 42 5.2.1 Deadlock Detection in MRS Since the considered MRS is fully distributed, each robot individually checks if the system is in a deadlock. But before the robots that are in the wait state start checking for deadlocks in the system, they have to identify each other and share the required information with one another. Following are the steps taken by each initiating robot in a wait state to detect deadlocks in the system: • Step 1: Besides sending a help signal, a robot in the wait state, starts broadcasting a new signal called wait signal, which encompasses local information about the task, resources allocated and resources requested. • Step 2: If the robot gets a response for its help signal, it will exit the wait state and will proceed with the task execution. However, if the robot receives a wait signal from another robot in the wait state, it will go to step 3 and will check for system deadlocks. • Step 3: Using Coffman’s algorithm, the robot checks if the system is in a deadlock or not. A detailed explanation on implementing the Coffman’s algorithm on MRS is given in the next section. • Step 4: If it is detected that system is in a deadlock, an initiating robot proceeds to the recovery stage, in which one of the initiating robots (and its cooperating robots) will eventually leave its task. • Step 5: If through Coffman’s method, the robot detects that the system is not in a deadlock, it returns to Step 1. 43 5.2.2 Applying Coffman’s Deadlock Detection Algorithm to MRS In Coffman’s deadlock detection approach, it is assumed that at any time in the system, the number of the resources allocated and requested is known. The multi-robot system that is developed in the present thesis, however, is fully distributed and there is no central unit for the robots to access the global information on the number of resources requested or acquired by the other tasks. Instead, in the proposed algorithm, upon identifying each other, the robots in the wait state share the local information by broadcasting them in the distributed network. The mapping of MRS on to the Coffman’s system is presented now. 𝒓𝒋 → resource types ~ types of sensors and actuators that the robots in the system own; including camera, bumper, gripper, and sonar sensors. 𝒘𝒋 → number of resources of each type ~ total number of a specific sensor or actuator in the system; for instance, total number of cameras in the system. 𝑻𝒊 → task i ~ objects in the wait state.  𝑇? directly corresponds to the initiating robot in the wait state that is leading the cooperative transportation of the object i. 𝒗𝒋 → number of available resources of each type ~ total number of sensors or actuators of a specific type that are readily available in the MRS; essentially it is the total number of robots having a specific type of sensor or actuator that are readily available. 𝑀𝑎𝑡𝑟𝑖𝑥  𝑷 → number of resources allocated to each task • 𝑝™ → number of resources of type j allocated to task i ~ total number of sensors or actuators of a specific type involved in handling object i. 𝑀𝑎𝑡𝑟𝑖𝑥  𝑸 → number of resources requested but not allocated to each task 44 • 𝑞™ → number of resources of type j requested by task i that are not yet allocated ~ total number of sensors or actuators of a specific type requested by the initiating robot handling object i that are not yet allocated Upon identifying other robots in the wait state and acquiring information about the tasks they are handling, every initiating robot uses Coffman’s algorithm to detect if the system is in a deadlock. As in Coffman’s approach, for every resource of type j, 𝑣? is calculated as follows 𝑣? = 𝑤? − 𝑝™???? = 𝑤? − 𝑝™ + 𝑝™????,??? (5.1) Here, 𝑤? is available to all robots upon starting the system start; 𝑝™ = total number of resources of type j acquired by object k, which is the object that the robot itself is involved in handling it; 𝑝™????,??? = total number of resources of type j acquired by all other objects in the wait state except object k. This is calculated using information received from other robots in the wait state. If for none of the objects i, 𝒗𝒋 ≥ 𝒒𝒊𝒋, the system is in a deadlock. In other words, if the number of available resources left in the system is not adequate to fulfill the request of any of the objects, the system is stuck in a deadlock situation. If the system is in a deadlock, each of the initiating robots in the wait state, autonomously and individually detects it and will proceed with the recovery plan. In the recovery stage, each robot calculates and broadcasts its cost of leaving its object. Each robot then compares its cost with others costs and ultimately the robot with the minimum cost will leave its task and will signal its cooperating robots to leave the task as well. This cost of leaving is a function of the 45 object’s distance to the goal location. Once robots leave the object, they return to the wandering state and are available to help transporting other objects in the system. The proposed MRS featuring deadlock detection and recovery method is verified through simulation. The simulation result is presented in section 5.3.2. 5.2.3 Detection-Based Control Framework for MRS – Approach 2 The detection-based algorithm is combined with the multi-robot cooperation algorithm. This second control framework for task execution by an MRS is presented in the flowchart of figure 13. Figure 13 - Detection-Based Task Execution Algorithm for MRS. 46 5.3 Simulation Results To verify the developed two control frameworks, both systems – prevention-based and detection-based systems – are simulated on the Webots simulation platform. The simulated system is composed of multiple heterogeneous robots and objects. However, simulating the system allows for extending the number of robots and objects in the system and hence provides much greater flexibility for system evaluation. Like the real physical pioneer robots, each simulated robot is equipped with a different set of sensors and has a certain payload capacity. These robotic capabilities, which constitute the system resources, include cameras, sonar sensors, bumpers and grippers. Similar to the real physical experiments, the goal of the developed MRS is to cooperatively transport multiple objects to a specific goal location as determined in advance for the system. The developed algorithms that are simulated on MRS comprise of a team of up to five pioneer robots. Figure 14 represents the multi-robot system simulation environment. Figure 14 - Multi-Robot System Simulation Environment. Robot 1 Robot 2 Robot 3 Robot 4 Robot 5 Object 2 Object 3 Object 1 Obstacle Obstacle 47 The coordinates of the goal location are pre-specified to the system. For simulation purposes the far end of the workspace is set as the goal location. To visualize, the designated goal location is shown as the hatched area in figure 14. The robots are required to cooperatively transport all the objects in the environment to the goal location. As indicated in Figure 14, the boxes with color stickers on them are the objects to be transported and the cone shaped objects are the obstacles to be avoided by the robots. The five simulated pioneer robots and their unique sets of sensing and actuating capabilities and maximum payload capacities are presented in table 5.1. Like the real physical experiments, it is assumed that the robots would identify some properties and partially required capabilities for each object through the color stickers attached to them. Table 1 – Simulated Pioneer Robots. Pioneer Robots Robot Capabilities Simulated Type Camera Bumper (Push) Gripper (Pick) Sonar GPS & Compass Payload P3DX ✓ ✗ ✓ ✓ ✓ 17 Kg P3AT ✓ ✓ ✗ ✓ ✓ 12 Kg P3DX ✓ ✓ ✗ ✓ ✓ 17 Kg P3DX ✗ ✓ ✗ ✓ ✓ 17 Kg P3DX ✓ ✓ ✗ ✓ ✓ 17 Kg Both multi-robot cooperation algorithms developed in the previous sections have been verified on various different multi-robot systems comprising number and types of objects. 48 5.3.1 MRS Featuring Deadlock Prevention A sample simulation result of a multi-robot system featuring deadlock prevention approach is presented now. The system is comprised of five robots and three objects labeled with red, green and blue stickers. Initially the robots start wandering and searching for the objects in the environment. Once an object with the color blob is detected, the robot identifies the partial required capabilities and if it acquires them, the robot will approach the object to attempt to transport the object individually. In figure 15, robots 1, 2, and 3 concurrently detect an object and start attempting to individually transport their objects to the goal location. Figure 15 - Individual Attempts. If the initial attempt is successful, the robot transports the object to the goal location and then it returns to the wandering state to search for more objects in the workspace. However, if the attempt fails, the initiating robot will broadcast a help signal to get another robot for cooperation. Among the robots in the wandering state, the robot that best fits the task will approach the initial robot for the cooperative attempt. 49 In figure 16, object 1 is successfully transported while robots 4 and 5 have come to cooperate with robots 2 and 3. Figure 16 – Cooperative Attempts. If the cooperative attempt is also failed, the initiating robot will again broadcast a help signal to acquire further assistance. If upon broadcasting the help signal, the initiating robot determines that there is no robot with the required partial capabilities available to cooperate, it will leave its object and release its cooperative robots to avoid potential system deadlock. In figure 17, robot 2 and 4 leave object 2 and return to wandering state to prevent the system from getting into a deadlock. Figure 17 - Robots Leave the Object to Prevent System Deadlock. 50 Now if any other cooperative attempt fails, these robots in the wandering state are available to help in object transportation. In figure 18, robots 1 and 2 are wandering in the workspace while robot 4 has joined robots 3 and 5 and together they successfully transport object 3 to the goal location. Figure 18 - Cooperative Object Transportation. Robots in the wandering state search for objects in the environment and if an object is detected again, the robot will begin with its individual attempt for task execution. If the individual attempt fails, the robot will request help. This will continue until the robots are successful and can cooperatively transport the object to the goal location. Figures 19 through 22 illustrate the step-by-step progress in handling object 2 from the moment robot 2 detects it. It starts with the initial and individual attempt of robot 2 and then shows the successive cooperation failures until eventually the object is successfully transported by four robots. 51 Figure 19 - Unsuccessful Individual Attempt. Figure 20 – First Unsuccessful Cooperation Attempt. Figure 21 – Second Unsuccessful Cooperation Attempt. 52 Figure 22 – Successful Cooperative Object Transportation. Once the object is transported, all the cooperating robots return to the wandering state and start searching the work environment for more objects. The multi-robot cooperation algorithm developed in section 5.1 is run multiple times on various work environments - comprising different number of objects. The simulation results verify that in the developed MRS deadlocks are successfully prevented. A drawback of this approach, however, is that the efficiency of the system decreases because the robots may leave their objects even when the system is not in a deadlock state. Once the robot(s) leave an object, that object has to be re-detected and handled later in the system. 5.3.2 MRS Featuring Deadlock Detection and Recovery In this section a sample simulation run of the multi-robot system incorporating deadlock detection and recovery is presented. The workspace is set exactly the same as the simulation run of the prevention method in the previous section. This is to illustrate how the two approaches resolve the same deadlock scenario in an MRS. The system comprises of five robots and three objects. The robots start by searching the environment and upon object detection each robot makes its individual attempt to transport the object. This is illustrated in figure 23. 53 Figure 23 – Robots Individual Attempts. If an individual attempt is unsuccessful, the robot broadcasts a help signal. If a robot with the required capabilities is available to help, the original robot waits for the cooperating robot to reach the object to begin the second attempt. If the cooperation attempt is also unsuccessful, the robots request for additional help. In figure 24, robot 2 is waiting for robot 5 to reach object 2 while robots 3 and 4 have asked for additional help. However, since no robot is available to help, robot 3 enters the wait state in which it begins broadcasting a wait signal along with a help signal. Figure 24 – Robots Cooperation Attempt. 54 In figure 25, cooperation attempt to push object 2 also fails and because still no robot is available to help, robot 2 also enters the wait state. Once the two robots in the wait state identify each other through the wait signals, they start to examine if the system is in a deadlock. Figure 25 – System Stuck in a Deadlock Situation. If it is detected that the system is in a deadlock, one of the robots 2 or 3 that has the minimum cost and its cooperating robots will leave their object and thus will be available to join another robot coalition to transport the object. In the current example, robots 3 and 4 leave their object (3) and return to wandering state. While wandering about, robot 3 receives the help signal of robot 2 and approaches object 2 to cooperate, as illustrated in figure 26. Figure 26 – Deadlock Resolved. 55 The initiating robot continues to request for additional help until the cooperation attempt is successful and object 2 is transported, as shown in figure 27. Figure 27 – Cooperative Object Transportation. Once object 2 is pushed to the goal location, the robots return to the wandering state. While searching, robot 2 detects object 3. As figures 28 through 30 illustrate, initially robot 2 is unsuccessful in its individual attempt and twice asks for an additional robot to help until eventually the three robots cooperatively transport object 3. Figure 28 – Individual Attempt. 56 Figure 29 – First Cooperation Attempt. Figure 30 – Transporting the Last Object. Eventually, all the objects are transported to the designated location. In the simulation results given above, the system was once stuck in a deadlock state, which was autonomously resolved through the detection and recovery method. In summary, in the present section the feasibility of the deadlock resolution approaches developed in this chapter was verified through simulating the developed MRS control frameworks on various unknown, unstructured, and dynamic multi-robot setups. An example simulation result of each of the developed approaches was presented to show the results of incorporating the deadlock resolution approaches into the multi-robot cooperation algorithm developed in chapter 3. Each of the developed approaches was tested on about fifty different 57 multi-robot simulation setups. These results are used in the next section to compare the two deadlock resolution methods in the context of multi-robot systems. See appendix A for simulation results. 5.4 Comparison of the Two Approaches The developed systems have been simulated on various mutli-robot setups. The results are presented in this section. The various setups established different environments for robots to operate in and resulted in a wide range of scenrios to evaluate the developed algorithms. The simulation environments or the setups comprised different number and types of objects that were randomly placed in the environment. Heterogenous objects introduced to the system were different in the partial capabilities that each required, in their sizes, and in their wieghts. The object weights are unkonw to the sysetm but essentially define the sizes of the robotic coalitions that are formed for object transportation. The coalition size of an object refers to the number of robots that are eventaully required to transport that object. To generate results for a fair comparison of the two systems, they have been simualted on exactly the same simulation setups. Over fifity different setups have been designed and each system has been simulated multiple times on each setup. The criteria for comparison of the two methods are the task completion time and the communication burden due to inter-robot communication. The total number of messages sent by the robots in each run are counted and used as the communication burden on the system. The task completion time is considered as the time it takes to tranport all the ojbects in the sytem to the designated goal location. From physical experiments it was recognized that as the number of objects and the coalition sizes were increased in the system, the number of deadlocks inceased correspondingly. This is 58 confirmed by the simulation data presented in figure 31. The x-axis repressents the number of objects in a task, y-axis represents the sum of the sizes of the robotic coalitions for the objects in each task, and the z-axis indicates the number system deadlocks in each task. It is observed that as the number of objects and the total coalition sizes get larger, the number of deadlocks in the sytstem increases correspondingly. Figure 31 – The Effect of Coalition Sizes and Number of Objects on the Number of System Deadlocks. In figure 31, each data point represents the number of system deadlocks in a single task as a function of the number of objects and the sum of coalition sizes for the task. Figure 32 presents the average task completion times as a function of the number of objects transported. It indicates that for both deadlock detection- and deadlock prevention-based systems, the task completion time grows as the number of objects increases. However, it indicates that it takes longer for the prevention-based MRS to complete its task as compared to detection-based systems. But the key point in the graph is that the gap between the completion times gets larger as the number of objects in the system is increased. This is due the fact that the probability of system deadlocks increases as the number of objects is increased. For the 59 prevention-based approach this directly corresponds to the number of times initiating robots leave their objects to avoid deadlocks in the system. The same argument is valid for the coalition sizes because as the objects in a task require a larger number of robots for cooperation, the chances of system deadlocks are greater. As discussed earlier, the drawback of the prevention method is that the robots may leave the object even when the system is not necessarily in a deadlock state, and when the robots leave the object, it has to be re-detected and re-handled later. That would result in a longer completion time. This is illustrated in figures 32 and 33. Figure 32 –The Effect of Number of Objects on Average Task Completion Time. 60 Figure 33 –The Effect f Coalition Sizes on Average Task Completion Time. Another criterion considered for the comparison of the two approaches is the communication burden on the system due to the signals and messages broadcasted in the system. The communication burden is measured as the total number of messages broadcasted by all the robots in the system. As the simulation results in figure 34 suggest, for both detection and prevention methods the number of messages sent increases as the number of objects in a task increases; however, the growth is more significant in the detection approach compared to the prevention approach. As the graphs in figure 34 indicate, for a task with a single object, the average number of messages sent is the same in both approaches; however, when the number of objects increases, the gap between them grows. This is due to the fact that in the detection approach, when the system is in a deadlock, extra messages carrying wait signals and leaving costs are broadcasted to detect and recover from the deadlock state. Figure 35 presents the increased communication burden due to the increased coalition sizes of the objects in the system. From both figures it can be concluded that detection-based systems generally have a larger communication burden compared to prevention-based systems. 61 Figure 34 – Communication Burden Due to the Number of Objects in the Task. Figure 35 – Communication Burden Due to the Coalition Sizes. In summary, from the simulation results it can be concluded that for small numbers of objects and for objects where small robotic coalitions are required, the deadlock detection and recovery approach dominates as it takes less time to complete the task and only slightly adds to the communication burden. Notice that the coalition size of an object is directly proportional to the weight of the object, and a smaller coalition size corresponds to a lighter object. However, as 62 the number of objects or object weights gets larger, the communication burden of the detection method becomes significantly larger than that of the prevention method, and if the design requirements allow for larger task completion times, the prevention method would be the preferred approach. 63 Chapter 6Conclusion Robotic systems can replace humans in hazardous applications like search and rescue operations, in applications where humans cannot perform the tasks by themselves like space explorations, applications where robots are preferred as in round-the-clock homecare applications, and in applications where robots have better performance than humans as in some industrial applications. In such applications, utilizing a cooperative multi-robot system (MRS) could increase the efficiency and quality of the solution. Therefore, MRS are of great importance in the field of robotics and a significant amount of research has been done in the field of MRS. Research in this thesis was focused on developing an MRS for multiple object transportation in an unknown, dynamic and unstructured environment. The main contributions of this thesis work are summarized next. 6.1 Primary Contributions In this thesis, two control frameworks that use AIS have been developed for an autonomous and cooperative MRS. Multi-robot cooperation in these system frameworks are based on Jerne’s Idiotypic Network Theory. Both systems are designed for simultaneous multi-object transportation and are also designed to autonomously resolve conflicts of shared resources that arise due to concurrent task executions. One system framework is developed based on the principles of deadlock prevention. Simulation results suggest that this approach is suitable for applications where the number of 64 objects and their weights are relatively large. Prevention-based approaches best suit applications where the number of objects is approximately more than five. The second control framework known as the detection-based MRS utilizes Coffman’s deadlock detection and recovery policy to identify system deadlocks and further recover from them to resolve conflicts of shared resources in the system. From the simulation results, it is concluded that detection-based MRS is suitable for applications where there are fewer objects in the environment and the objects do not require large number of robots to be transported. 6.2 Strengths and Limitations Strengths of the developed MRS are summarized in the following: • System is flexible to changes in the environment and in the composition of robots in the system. It operates in unknown, dynamic, unstructured environments where random objects and obstacles are introduced into the system. Also if robots composition is changed due to introduction of a new robot to the system or removal of a malfunctioned robot, system will adapt to the changes and robots will proceed with their operations. • System takes advantages of a fully distributed. There is no central controller or leader to coordinate actions of the robots in the system and failure of a robot would not cripple the system, rather the system will adapt without noticeable degradation in its performance. Robots only have local knowledge and if required they share it with each other through dynamic network communications. • System’s robustness is increased by taking advantage of parallelism and redundancy of multiple robots in the system and by incorporating autonomous deadlock resolution algorithms to resolve conflicts in distribution of shared resources in the system. 65 Limitations of the MRS developed are as follows: • System best suits small to medium size MRS because as the number of robots increases, they become as obstacles for one another and make it more challenging for themselves to detect and transport objects in the environment. Furthermore, as the number of robots increases, the communication burden on the system grows exponentially and surpassing certain number of robots in the system would degrade the overall performance of the system substantially. • Although the developed system is robust and adapts to robot failures, system does not have the ability to detect robot failures autonomously and if any robot fails it does not communicate its failure with others. Furthermore, system is not capable of detecting the malfunctions neither at the robot level nor team level. 6.3 Suggested Future Work As stated, a major limitation of the developed system is the lack of a fault detection mechanism in the system. In future, a fault detection mechanism may be implemented to let the system autonomously detect failures at both robot level and team level and to communicate the failure with other robots in the system. Furthermore, the system performance can be improved by incorporating a learning mechanism so that the robots can remember and learn from their past experiences and use it to improve their future task executions in the system. Finally, it was assumed that some prosperities and partial required capabilities of the objects were obtained through color-blob detection. These include object position, object dimensions, and some sensing and actuating capabilities required to handle the object. Methods exist in the 66 real world to actually detect these properties and these mechanisms can be incorporated into the developed system to make it better suit real life applications. 67 Bibliography Ballal, P., Giordano, V., & Lewis, F. (2006, June). Deadlock free dynamic resource assignment in multi-robot systems with multiple missions: a matrix-based approach. 14th Mediterranean Conference on Control and Automation , 1-6. Bhatia, S., & Iiyas, M. (1990). Evaluation of Interprocessor Communication Overhead in Distributed Computer Systems. Computers and Industrial Engineering , 11 (4), 425-434 . Botelho, S., & Alami, R. (1999). M+: a scheme for multi-robot cooperation through negotiated task allocation and achievement. IEEE International Conference on Robotics and Automation, 1999. Proceedings. , 2, 1234 - 1239. Capitan, J., Spaan, M. T., Merino, L., & Ollero, A. (2013). Decentralized multi-robot cooperation with auctioned POMDPs . The International Journal of Robotics Research , 32 (6), 650-671. Coffman, E. G., Elphick, M. J., & Shoshani, A. (1971). System Deadlocks. ACM Computing Surveys (CSUR) , 3 (2), 67-78. de Hoog, J., Cameron, S., & Visser, A. (2009, November). Role-Based Autonomous Multi-Robot Exploration . Computation World: Content, Patterns , 482 - 487. Dhiraj, G., & V.K., G. (2012). Approaches for Deadlock Detection and Deadlock Prevention for Distributed systems . Research Journal of Recent Sciences , 1, 422-425. Dijkstra, E. W. (2002). Cooperating sequential processes. In P. B. Hansen, The Origin of Concurrent Programming: From Semaphores to Remote Procedure Calls (pp. 65 - 138 ). Syracuse, New York, USA: springer-verlag. Ding, Y., Zhu, M., He, Y., & Jiang, J. (2006). An Autonomous Task Allocation Method Of The Multi-Robot System . 9th International Conference on Control, Automation, Robotics and Vision . Gao, Y., & Luo, Z. (2008, June). Dynamic Task Allocation Method Based on Immune System for Cooperative Robots. Proceedings of the 7th World Congress on Intelligent Control and Automation, Chongqing, China . Gao, Y., & Wei, W. (2005, April). A New Multi-Robot Self-Determination Cooperation Method Based on Immune Agent Network . Proceedings of the 2005 IEEE International Conference on Robotics and Automation , 390-395 . Gao, Y., & Wei, W. (2006). Multi-Robot Autonomous Cooperation Integrated with Immune Based Dynamic Task Allocation. Sixth International Conference on Intelligent Systems Design and Applications , 2, 586-591. 68 Gautam, A., & Mohan, S. (2012, August). A review of research in multi-robot systems. 2012 7th IEEE International Conference on Industrial and Information Systems (ICIIS), Chennai , 1-5. Gerkey, B. P., & Mataric ́, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems . The International Journal of Robotics Research , 23 (9). Gerkey, B., & Mataric, M. (2002). Sold!: Auction Methods for Multirobot Coordination . IEEE Transactions on Robotics and Automation , 18 (5), 758 - 768 . Ghosh, S. (2007). Distributed Systems: An Algorithmic Approach. Boca Raton: Chapman & Hall/CRC. Habermann, A. N. (1969). Prevention of System Deadlocks . Communications of the ACM , 12 (7), 373-385. Holt, R. C. (1971). Comments on Prevention of System Deadlocks . Communications of the ACM , 14 (1), 36-38. Jiang, L., & Zhang, R. (2011). An Autonomous Task Allocation for Multi-robot System . Journal of Computational Information Systems , 7 (11), 3747-3753 . Kalra, N., & Martinoli, A. (2006). A Comparative Study of Market-Based and Threshold-Based Task Allocation. Proceedings of the 8th International Symposium on Distributed Autonomous Robotic Systems (DARS) . Khan, M. T.(2010). Robust and autonomous multi-robot cooperation using an artificial immune system(Doctoral dissertation). University of British Columbia's Digital Repository cIRcle. Khan, M. T., & Silva, C. W. (2008 , September). Autonomous Fault Tolerant Multi-Robot Cooperation Using Artificial Immune System . Proceedings of the IEEE International Conference on Automation and Logistics, Qingdao, China . Khan, M. T., & de Silva, C. (2009, March). Autonomous fault tolerant multi-robot coordination for object transportation based on Artificial Immune System. Second International Conference on Robot Communication and Coordination , 1-6. Khan, M. T., Imanuel, T., & Silva, C. W. (2010, June). Autonomous Market-Based Multi-Robot Cooperation . 2010 International Conference on Intelligent and Advanced Systems (ICIAS), Kuala Lumpur, Malaysia . 69 Korsah, G. A., Stentz, A., & Dias, M. B. (2013). A comprehensive taxonomy for multi-robot task allocation . The International Journal of Robotics Research , 32 (12), 1495–1512 . Kube, C., & Bonabeau, E. (2000). Cooperative transport by ants and robots . Robotics and Autonomous Systems , 30 (1-2), 85-101. Lang, S.-D. (1999). An Extended Banker’s Algorithm for Deadlock Avoidance . IEEE Transactions on Software Engineering , 25 (3), 428-432. Lau, H. Y., & Wong, V. W. (2006). An Immunity-Based Distributed Multiagent-Control Framework . IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans , 36 (1), 91-108 . Mataric, M., Nilsson, M., & Simsarin, K. (1995). Cooperative multi-robot box-pushing. Intelligent Robots and Systems 95. 'Human Robot Interaction and Cooperative Robots', Proceedings. 1995 IEEE/RSJ International Conference on , 3, 556 - 561 . Matsumoto, A., Asama, H., Ishida, Y., Ozaki, K., & Endo, I. (1990). Communication in the autonomous and decentralized robot system ACTRESS. Intelligent Robots and Systems '90. 'Towards a New Frontier of Applications', Proceedings. IROS '90. IEEE International Workshop on , 2, 835 - 840. New York University. (2002, March 20). Deadlock Prevention, Avoidance, Detection and Recovery. Retrieved April 25, 2014, from New York University: Computer Science: http://www.cs.nyu.edu/courses/spring02/V22.0202-001/lectures/lect11.pdf Nezu, K. (1980, May). System Deadlocks Resolution. Proceedings of the national computer conference , 257-260. Nitzberg, B., & Lo, V. (1991). Distributed Shared Memory: A Survey of Issues and Algorithms. Computer , 24 (8), 52-60. Parker, L. E. (1998). ALLIANCE: An Architecture for Fault Tolerant Multirobot Cooperation. IEEE Transactions on Robotics and Automation , 14 (2), 220-240. Parker, L. E. (2003). Current research in multirobot systems . Artificial Life and Robotics , 7 (1-2), 1-5. Parker, L. E. (2008). Distributed Intelligence: Overview of the Field and its Application in Multi-Robot Systems . Journal of Physical Agents (special issue on multi-robot systems) , 2 (1), 5-14. Parker, L., & Tang, F. (2006). Building Multirobot Coalitions Through Automated Task Solution Synthesis. Proceedings of the IEEE , 94 (7), 1289-1305 . 70 Rosenkrantz, D. J., Stearns, R. E., & Philip M. Lewis, I. (1978). System Level Concurrency Control for Distributed Database Systems . ACM Transactions on Database Systems , 3 (2), 178-198 . Singhal, M. (1989). Deadlock detection in distributed systems. Computer , 22 (11), 37-48 . Tang, F., & Parker, L. (2007). A Complete Methodology for Generating Multi-Robot Task Solutions using ASyMTRe-D and Market-Based Task Allocation. Proc. of IEEE International Conference on Robotics and Automation, Rome, Italy , 3351 - 3358. University of British Columbia . (2013). EECE 314 System Software Engineering . Retrieved May 29, 2014, from EECE UBC: https://courses.ece.ubc.ca/314/ Wang, J.-P., Gu, Y., & LI, X.-M. (2012). Multi-robot Task Allocation Based on Ant Colony Algorithm . Journal of Computers , 7 (9), 2160-2167. Wang, Y., & de Silva, C. W. (2005, June). An Object Transportation System with Multiple Robots and Machine Learning. 2005 American Control Conference, Portland, OR, USA . Werger, B., & Mataric, M. (2000). Broadcast of Local Eligibility: Behavior-Based Control for Strongly Cooperative Robot Teams. Proceedings of the Fourth International Conference on Autonomous Agents , 21-22. Whitbrook, A. M., Aickelin, U., & Garibaldi, J. M. (2007). Idiotypic Immune Networks in Mobile-Robot Control . IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics , 37 (6), 1581 - 1598. Xu, X., Zu, L., Chen, L., & Zhang, X. (2007, December). Cooperative Task Allocation of Multi-robots System in Complex Environment. Proceedings of the 2007 IEEE International Conference on Robotics and Biomimetics, Sanya, China , 565-570. Yan, Z., Jouandeau, N., & Cherif, A. A. (2013). A Survey and Analysis of Multi-Robot Coordination . International Journal of Advanced Robotic Systems , 10. Zhang, D., Xie, G., Yu, J., & Wang, L. (2007). Adaptive task assignment for multiple mobile robots via swarm intelligence approach . Robotics and Autonomous Systems , 55, 572–588 . 71 Appendices Appendix A Simulation Data Data collected from simulation runs are presented in this appendix. Graphs presented in Chapter 5 are based on this data. A.1 Prevention-based MRS Simulation Data In table 2, simulation results for the prevention-based control framework are summarized. Exp Scenario column represents the coalition sizes of the objects that are required for the objects introduced to the system. For instance, (1, 2, 4) represents that the first, second and the third object correspondingly required 1, 2, and 4 robots to be transported. The # of messages is the total number of messages broadcasted in the system in each run. # of coalitions is the sum of coalitions in each run; for example, for (1, 2, 4) total coalition would be 7. For each scenario the MRS has been run multiple times and the average data is presented in table 2 in the next page. 72 Table 2 - Simulation Results of Prevention-Based MRS. In the next set of tables, the results from the simulation runs of 1, 2, 3, and 4 objects are presented. Simulation results are for the scenario where three objects are introduced to the system. The coalition sizes have been varied as shown in the Exp Scenario column of the table. The time the system takes to finish the tasks and the number of messages that are broadcasted are collected for further analysis. For each coalition scenario, the positions of the objects have been changed to test the developed system on as many various environments as possible. 73 Table 3 - Prevention-Based System Runs for One Object. Table 4 - Prevention-Based System Runs for Two Objects. 74 Table 5 - Prevention-Based System Runs for Three Objects. Table 6 - Prevention-Based System Runs for Four Objects. 75 A.2 Detection-based MRS Simulation Data Table 7 is similar to table 2 except that it has a column that represents the number of times system gets into the deadlock in run. Table 7 - Simulation Results of Detection-Based MRS. Similarly data for simulation results of different number of objects for detection-based system is presented in the tables 8 through 11. Table 8 - Detection-Based System Runs for One Object. 76 Table 9 – Detection-Based System Runs for Two Objects. Table 10 – Detection-Based System Runs for Four Objects. 77 Table 11 – Detection-Based System Runs for Three Objects. 78 Appendix B Effect of Increasing the Number of Robots on the MRS As Khan (2010) indicated in his dissertation, as the number of robots in the environment exceeds 13 robots the average task complete time and the number of messages broadcasted increase greatly. The following figures have been acquired from Khan’s dissertation (Khan, 2010). Figure 36 – Effect of Number of Robots on Task Completion Time. Figure 37 – Effect of Number of Robots on Task Completion Time. 79 Appendix C Pioneer Robot Sensors and Actuators C.1 Real Physical Robots in IAL Figure 38 – Real Simulated P3DX and P3AT. C.2 Simulated Robots in Webots Simulation Platform Figure 39 - Simulated P3DX and P3AT. """@en ; edm:hasType "Thesis/Dissertation"@en ; vivo:dateIssued "2014-11"@en ; edm:isShownAt "10.14288/1.0167264"@en ; dcterms:language "eng"@en ; ns0:degreeDiscipline "Mechanical Engineering"@en ; edm:provider "Vancouver : University of British Columbia Library"@en ; dcterms:publisher "University of British Columbia"@en ; dcterms:rights "Attribution-NonCommercial-NoDerivs 2.5 Canada"@en ; ns0:rightsURI "http://creativecommons.org/licenses/by-nc-nd/2.5/ca/"@en ; ns0:scholarLevel "Graduate"@en ; dcterms:title "Autonomous and cooperative multi-robot system for multi-object transportation"@en ; dcterms:type "Text"@en ; ns0:identifierURI "http://hdl.handle.net/2429/50337"@en .