Intelligent Collaboration among Robotic Agents for Landmine Detection VAITHILINGAM KUMARATHASAN This thesis was submitted to the department of Electrical Engineering of University of Moratuwa in partial fulfillment of the requirements for the Degree of Master in Science Department of Electrical Engineering University of Moratuwa Sri Lanka November 2004 Supervisor: Thrishantha Nanayakkara PhD i Declaration The work submitted in this thesis is the result of my own investigations, except where stated. It has not already been accepted in substance for any degree, and also not being concurrently submitted for any other degrees. V. Kumarathasan Candidate Dr. DPT Nanayakkara Supervisor ii Dedication To my beloved parents Ramanathar Vaithilingam and Pakkiyaledsumi Vaithilingam iii Abstract Landmines remain as a significant barrier to economic and social development for more than sixty countries including Sri Lanka. Once a conflict comes to an end, the areas where landmines have been laid have to be cleared for human re-settlement. Demining is an operation accompanied with a lot of risk to human deminers. Analysis of the actions of the human deminers shows that some of them could be more easily and safely performed by robotic systems. From this perspective these robotic systems appear to have an important role to play in finding and removing millions of landmines from around the world. This thesis proposes a novel algorithm for multi-robot collaboration for landmine search operations. The challenge is to enable robots to work together in an intelligent manner to detect landmines as fast as possible. Collaboration among robots is based on a decentralized approach in which robots are based on a set of behaviors; such behaviors are designed to increase global performance and are based in local information and shared information from other team members whenever they are within the range of communication. Landmine search method is improved using the prior knowledge about landmine field. The effectiveness of the algorithm is demonstrated using extensive simulation studies. Result shows that collaboration of robotic agents and use of information about mine fields reduces the landmines search time dramatically. iv Acknowledgements I would like to thank my supervisor, Dr. Thrishantha Nanayakkara for his guidance throughout the project. He has provided me with invaluable advice on which direction my project should take and what I should focus on. He has made it a point to visit the students working in the laboratory and see if we have any problems. I convey my humble gratitude to Dr Nalin Wickramarachchci and Dr. Nishantha Nanayakkara for their valuable comments and suggestions. I also thank the progress review panel Prof H. Sriyananatha, Dr. HYR Perera and Dr L Udawatta for their suggestions to improve my work. My deep, respectful gratitude goes to ADB and NSF for funding the project and special thanks go to Prof (Mrs.) N. Ratnayake, who made tremendous effort to award ADB scholarship. I also thank Dr. R. G. N. De. S. Munasinghe, Director, Postgraduate studies and his staff for the support and guidance given to me. My sincere thank goes to Prof JR Lucas, former head of the department and Dr. Ranjith Perera, present head of the department for their valuable guidance and the support given to me during difficulties. I also thank the technical officers from the department for their support given to me. I would also like to thank my peers, Ampikathasan Aravinthan and Visvakumar Aravinthan for their insightful comments and help. They have provided a different perspective for solving the problems I faced. Last but not least I thank my parents for their support to lift me whenever I underwent difficulties and for their love v Contents Chapter Page 1 Introduction 1 1.1 Impacts of landmines on the Community 1 1.2 Robotic Demining 4 1.3 Scope of Thesis 5 1.4 Structure of Thesis 6 2 Multirobot Coordination 7 2.1 Multirobot System 7 2.2 Control and Coordination of Multiple Mobile Robots 8 2.2.1 Autonomous Mobile Robots 8 2.2.1.1 Subsumption Architecture 8 2.2.1.2 Autonomous Navigation 9 2.2.2 Multirobot Systems 10 2.2.3 Self Organizing System 11 2.2.3.1 Characteristics of Self-Organizing Systems 12 2.2.3.2 Advantages of Self-Organization 13 2.2.3.3 Natural Systems 14 2.2.4 Related work in multirobot search operation 17 vi 3 Methodology 20 3.1 Decentralised Coordination and Architecture 20 3.2 Use of Knowledge about Landmine Field 21 3.3 Task Creation Using Search Techniques 23 3.3.1 Self Organizing Behaviour 24 3.3.2 Search Method For Some Knowledge About Landmine Field Scenario 28 3.3.2.1 Determination of Orientation of Landmine laid pattern 28 3.3.3 Search method for perfect knowledge scenario 33 4 Technical Assessment 35 4.1 Navigation module 35 4.2 Landmine detection module 38 4.3 Localization module 39 4.4 Communication module 42 4.5 Conclusion 43 5 Results and Analysis 44 5.1 Simulation Setup 44 5.2 Search result for perfect knowledge scenario 45 5.3 Search result for some knowledge scenario 46 5.4 Search result for without knowledge scenario 47 5.5 Performance of search methods and area covered 51 5.6 Comparison of results obtained in three search methods 53 6 Conclusions 56 vii List of Figures and Tables Figure 1.1: Landmine casualty in different age groups in Sri Lanka 2 Figure 3.1: Layered multirobot architecture 21 Figure 3.2a: Mine laying pattern type 1 22 Figure 3.2b: Mine laying pattern type 2 22 Figure 3.3: Bund and mine pattern layout 23 Figure 3.4 Known mine pattern and unknown orientation 23 Figure 3.5: For an example, if Robot R1 finds landmine it will create artificial field such that the robot R2 should change its heading by. toward the robot R1. 25 Figure3.6: Snap shot of simulations show that three robots are organized towards mine area by method of SOB 27 Figure 3.7a: Location of mine detected by three robots, case1 28 Figure 3.7b: Location of mine detected by three robots, case2 29 Figure 3.7c: Location of mine detected by three robots, case3 29 Figure 3.7d: Location of mine detected by three robots, case4 30 Figure 3.8: Search path of three robots after determining orientation of mine pattern 32 Figure 3.9: Snap shot of simulation showing search path of three robots in some knowledge about landmine field scenario 32 Figure 3.10: Search path of three robots after a robot has found a mine 33 Figure 3.11: Snap shot of simulation showing search path in perfect knowledge scenario. 33 Figure 4.1: Mine detection robot built at IARC navigate in rough terrain 36 Figure 4.2: Mine detection robot COMET II 37 Figure 4.3: Mobile robot (AMDR) built at our lab 38 Figure 5.1: Simulation fields with different arrangement of landmines 45 Figure 5.2: Total detected mines (%) over simulation steps for perfect knowledge scenario 45 viii Figure 5.3: Detected mine distribution over simulation steps for some knowledge scenario. 46 Figure 5.4: Detected mine distribution over simulation steps for some knowledge scenario. 46 Figure 5.5: Total detected mines (%) over simulation steps for some knowledge scenario 47 Figure 5.6: Search paths of SOB in the different mine fields 48 Figure 5.7: Total detected mines (%) over simulation steps for cluster scenario 48 Figure 5.8 Detected mine distribution over simulation steps for cluster scenario 49 Figure 5.9: Detected mine distribution over simulation steps for no knowledge scenario. 50 Figure 5.10: Total detected mines (%) over simulation steps for no knowledge 50 Figure 5.11: Mine detected (%) over covered area (%) in SOB 51 Figure 5.12: Mine detected (%) over covered area (%) in some knowledge case 52 Figure 5.13: Mine detected (%) over covered area (%) in perfect knowledge case 53 Figure 5.14: Detected mine distribution over simulation steps for different Scenario 54 Figure 5.15: Total detected mines (%) over simulation steps 54 Table 5.1: Performance of search methods 55 Chart 3.1: Algorithm for SOB 26 Chart 3.2: Algorithm for some knowledge case 31 Chart 3.3: Algorithm for perfect knowledge case 34