Path Planning of Cooperative Mobile Robots Using Discrete Event Models

Offers an integrated presentation for path planning and motion control of cooperative mobile robots using discrete-event system principles

Generating feasible paths or routes between a given starting position and a goal or target position—while avoiding obstacles—is a common issue for all mobile robots. This book formulates the problem of path planning of cooperative mobile robots by using the paradigm of discrete-event systems. It presents everything readers need to know about discrete event system models—mainly Finite State Automata (FSA) and Petri Nets (PN)—and methods for centralized path planning and control of teams of identical mobile robots.

Path Planning of Cooperative Mobile Robots Using Discrete Event Models begins with a brief definition of the Path Planning and Motion Control problems and their state of the art. It then presents different types of discrete models such as FSA and PNs. The RMTool MATLAB toolbox is described thereafter, for readers who will need it to provide numerical experiments in the last section. The book also discusses cell decomposition approaches and shows how the divided environment can be translated into an FSA by assigning to each cell a discrete state, while the adjacent relation together with the robot's dynamics implies the discrete transitions.

Highlighting the benefits of Boolean Logic, Linear Temporal Logic, cell decomposition, Finite State Automata modeling, and Petri Nets, this book also:

• Synthesizes automatic strategies based on Discrete Event Systems (DES) for path planning and motion control and offers software implementations for the involved algorithms
• Provides a tutorial for motion planning introductory courses or related simulation-based projects using a MATLAB package called RMTool (Robot Motion Toolbox)
• Includes simulations for problems solved by methodologies presented in the book

Path Planning of Cooperative Mobile Robots Using Discrete Event Models is an ideal book for undergraduate and graduate students and college and university professors in the areas of robotics, artificial intelligence, systems modeling, and autonomous control.

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 xi

Preface xv

Acknowledgments xvii

Acronyms xix

1 Introduction 1

1.1 Historical perspective of mobile robotics 1

1.2 Path planning. Definition and historical background 4

1.3 Motion control. Definition and historical background 9

1.4 Motivation for expressive tasks 11

1.5 Assumptions of this monograph 14

1.6 Outline of this monograph 14

2 Robot Motion Toolbox 17

2.1 Introduction 17

2.2 General description of the simulator 20

2.3 Path planning algorithms 25

2.4 Robot kinematic models 26

2.5 Motion control algorithms 29

2.5.1 Pure pursuit algorithm 29

2.5.2 PI controller 32

2.6 Illustrative examples 33

2.6.1 Examples about path planning aspects 33

2.6.2 Examples about motion control aspects 35

2.6.3 Examples about multi-robot systems and high-level tasks 37

2.7 Conclusions 40

3 Cell Decomposition Algorithms 41

3.1 Introduction 41

3.2 Cell decomposition algorithms 42

3.2.1 Hypothesis 42

3.2.2 Trapezoidal decomposition 45

3.2.3 Triangular decomposition 46

3.2.4 Polytopal decomposition 49

3.2.5 Rectangular decomposition 52

3.3 Implementation and extensions 53

3.3.1 Extensions 53

3.3.2 Implemented functions 55

3.4 Comparative analysis 58

3.4.1 Qualitative comparison 58

3.4.2 Quantitative comparison 61

3.5 Conclusions 70

4 Discrete Event System Models 71

4.1 Introduction 71

4.2 Environment abstraction 72

4.3 Transition system models 75

4.3.1 Single robot case 75

4.3.2 Multi-robot case 79

4.4 Petri net models 83

4.5 Petri nets in resource allocation systems models 90

4.6 High-level specifications 96

4.7 Linear temporal logic 100

4.8 Conclusions 106

5 Path Planning by Using Transition System Models 109

5.1 Introduction 109

5.2 Two-step planning for a single robot and reachability specification 110

5.3 Quantitative comparison of two-step approaches 115

5.4 Receding horizon approach for a single robot and reachability specification 119

5.5 Simulations and analysis 123

5.6 Path planning with an LTL

5.7 Collision avoidance using initial delay 132

5.7.1 Problem description 132

5.7.2 Solution for Problem 5.1 (decentralized) 135

5.7.3 Solution for Problem 5.2 (centralized) 137

5.8 Conclusions 139

6 Path and Task Planning Using Petri Net Models 141

6.1 Introduction 141

6.2 Boolean-based specifications for cooperative robots 144

6.2.1 Problem definition and notations 144

6.2.2 Linear restrictions for Boolean-based specifications 146

6.2.3 Solution for constraints on the final state 147

6.2.4 Solution for constraints on trajectory and final state 149

6.2.5 Discussion on the above solutions 151

6.2.6 Suboptimal solution 152

6.2.7 Simulation examples 154

6.3 LTL specifications for cooperative robots 157

6.3.1 Problem definition and solution 157

6.3.2 Simulation examples 167

6.4 A sequencing problem 170

6.4.1 Problem statement 170

6.4.2 Solution 175

6.5 Task gathering problem 180

6.5.1 Problem formulation 180

6.5.2 Solution 181

6.6 Deadlock prevention using resource allocation models 185

6.7 Conclusions 192

7 Concluding Remarks 193

Bibliography 195

Index 211

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.