Path Planning of Cooperative Mobile Robots Using Discrete Event Models

CRISTIAN MAHULEA, PHD, has participated in the development and implementation of Petri Net Toolbox and SimHPN, two MATLAB software for simulation, analysis and synthesis of discrete-event systems modeled with Petri Nets. His research interests include discrete event systems, hybrid systems, automated manufacturing, Petri nets, mobile robotics and healthcare systems. He participated in the development of RMTool, a collection of tools for modeling, path planning and motion control of mobile robots. MARIUS KLOETZER, PHD, developed two laboratory robotic platforms (at Boston University, USA, and at Technical University of Iasi, Romania) for facilitating real time experiments based on the proposed formal solutions. He is also participating in the development and extension of RMTool software package. His research interests include planning of mobile robots based on discrete abstractions and expressive specifications. RAMÓN GONZÁLEZ, PHD, is the founder and CEO of robonity, an MIT innovation-driven startup. Ramon is an authority on robotics and engineering whose skills have been demonstrated in some of the most important engineering centers in the world including a 3-year research position at the MIT Robotic Mobility Group. He has received several awards including the Medal of the Royal Academy of Engineering of Spain and the Medal of Andalucia (first in history to an engineer in robotics). He holds a PhD in robotics and an engineering degree in computer science by the University of Almeria (Spain) and a certificate in accounting and finance by the Imperial College Business School (UK).

• Foreword xiPreface xvAcknowledgments xviiAcronyms xix1 Introduction 11.1 Historical perspective of mobile robotics 11.2 Path planning. Definition and historical background 41.3 Motion control. Definition and historical background 91.4 Motivation for expressive tasks 111.5 Assumptions of this monograph 141.6 Outline of this monograph 142 Robot Motion Toolbox 172.1 Introduction 172.2 General description of the simulator 202.3 Path planning algorithms 252.4 Robot kinematic models 262.5 Motion control algorithms 292.5.1 Pure pursuit algorithm 292.5.2 PI controller 322.6 Illustrative examples 332.6.1 Examples about path planning aspects 332.6.2 Examples about motion control aspects 352.6.3 Examples about multi-robot systems and high-level tasks 372.7 Conclusions 403 Cell Decomposition Algorithms 413.1 Introduction 413.2 Cell decomposition algorithms 423.2.1 Hypothesis 423.2.2 Trapezoidal decomposition 453.2.3 Triangular decomposition 463.2.4 Polytopal decomposition 493.2.5 Rectangular decomposition 523.3 Implementation and extensions 533.3.1 Extensions 533.3.2 Implemented functions 553.4 Comparative analysis 583.4.1 Qualitative comparison 583.4.2 Quantitative comparison 613.5 Conclusions 704 Discrete Event System Models 714.1 Introduction 714.2 Environment abstraction 724.3 Transition system models 754.3.1 Single robot case 754.3.2 Multi-robot case 794.4 Petri net models 834.5 Petri nets in resource allocation systems models 904.6 High-level specifications 964.7 Linear temporal logic 1004.8 Conclusions 1065 Path Planning by Using Transition System Models 1095.1 Introduction 1095.2 Two-step planning for a single robot and reachability specification 1105.3 Quantitative comparison of two-step approaches 1155.4 Receding horizon approach for a single robot and reachability specification 1195.5 Simulations and analysis 1235.6 Path planning with an LTL5.7 Collision avoidance using initial delay 1325.7.1 Problem description 1325.7.2 Solution for Problem 5.1 (decentralized) 1355.7.3 Solution for Problem 5.2 (centralized) 1375.8 Conclusions 1396 Path and Task Planning Using Petri Net Models 1416.1 Introduction 1416.2 Boolean-based specifications for cooperative robots 1446.2.1 Problem definition and notations 1446.2.2 Linear restrictions for Boolean-based specifications 1466.2.3 Solution for constraints on the final state 1476.2.4 Solution for constraints on trajectory and final state 1496.2.5 Discussion on the above solutions 1516.2.6 Suboptimal solution 1526.2.7 Simulation examples 1546.3 LTL specifications for cooperative robots 1576.3.1 Problem definition and solution 1576.3.2 Simulation examples 1676.4 A sequencing problem 1706.4.1 Problem statement 1706.4.2 Solution 1756.5 Task gathering problem 1806.5.1 Problem formulation 1806.5.2 Solution 1816.6 Deadlock prevention using resource allocation models 1856.7 Conclusions 1927 Concluding Remarks 193Bibliography 195Index 211