Cristian Mahulea - Path Planning of Cooperative Mobile Robots Using Discrete Event Models

1 Cover

2 Foreword

3 Preface

4 Acknowledgments

5 Acronyms

6 Chapter 1: Introduction1.1 Historical perspective of mobile robotics 1.2 Path planning. Definition and historical background 1.3 Motion control. Definition and historical background 1.4 Motivation for expressive tasks 1.5 Assumptions of this monograph 1.6 Outline of this monograph

7 2 Robot Motion Toolbox2.1 Introduction 2.2 General description of the simulator 2.3 Path planning algorithms 2.4 Robot kinematic models 2.5 Motion control algorithms 2.6 Illustrative examples 2.7 Conclusions

8 3 Cell Decomposition Algorithms3.1 Introduction 3.2 Cell decomposition algorithms 3.3 Implementation and extensions 3.4 Comparative analysis 3.5 Conclusions

9 4 Discrete Event System Models4.1 Introduction 4.2 Environment abstraction 4.3 Transition system models 4.4 Petri net models 4.5 Petri nets in resource allocation systems models 4.6 High‐level specifications 4.7 Linear temporal logic 4.8 Conclusions

10 5 Path Planning by Using Transition System Models 5.1 Introduction 5.2 Two‐step planning for a single robot and reachability specification 5.3 Quantitative comparison of two‐step approaches 5.4 Receding horizon approach for a single robot and reachability specification 5.5 Simulations and analysis 5.6 Path planning with an specification 5.7 Collision avoidance using initial delay 5.8 Conclusions

11 6 Path and Task Planning Using Petri Net Models6.1 Introduction 6.2 Boolean‐based specifications for cooperative robots 6.3 LTL specifications for cooperative robots 6.4 A sequencing problem 6.5 Task gathering problem 6.6 Deadlock prevention using resource allocation models 6.7 Conclusions

12 7 Concluding Remarks

13 Bibliography

14 Index

15 IEEE PRESS SERIESONSYSTEMSSCIENCE AND ENGINEERING

16 End User License Agreement

1 Chapter 3Table 3.1 Properties (on rows) versus cell decomposition types (on columns).Table 3.2 Trends of metrics with respect to the number of obstacles: cost cri...

2 Chapter 4Table 4.1 Comparison between the discrete formalisms used in multi‐robot path...Table 4.2 Constants, Boolean and temporal operators used to define formulas....

3 Chapter 5Table 5.1 Cost and Time Complexity by varying and parameters.Table 5.2 Cost and Time Complexity by varying and parameters when the fina...Table 5.3 Cost and Time Complexity by varying for each different cell decomp...Table 5.4 Comparison of the performances by using different Intermediate Traj...

1 Chapter 1 Figure 1.1 Mobile robots and reactive navigation. Example of mobile robots b... Figure 1.2 Autonomous mobile robots. Example of pioneering autonomous mobile... Figure 1.3 Navigation architecture of a mobile robot. Example of a navigatio... Figure 1.4 Path planning methods. Main categories for path planning in mobil... Figure 1.5 Motion control methods. Main categories for motion control in mob... Figure 1.6 Path planning levels. Path planning levels of standard navigation... Figure 1.7 Expressive tasks. Meaning of expressive tasks.

2 Chapter 2 Figure 2.1 Simulators for path planning and motion control. Different simula... Figure 2.2 Main window of Robot Motion Toolbox (RMTool). Figure 2.3 Submenu with information about the configuration of the robot and... Figure 2.4 Robot configurations considered in the RMTool software. Figure 2.5 Pure Pursuit strategy.Figure 2.6 Simulations using different path planning approaches. Examples re...Figure 2.7 Simulations using different motion control approaches. Examples r...Figure 2.8 Examples related to multi‐robot systems and the LTL task by using...Figure 2.9 Examples related to multi‐robot systems and the Boolean task by u...

3 Chapter 3Figure 3.1 Example of an environment. An environment with three obstacles an...Figure 3.2 Trapezoidal decomposition example. Trapezoidal decomposition (con...Figure 3.3 Problems with the standard Delaunay decomposition. Attempting to ...Figure 3.4 Constraint triangular decomposition. Constrained triangular decom...Figure 3.5 Polytopal decomposition. Polytopal decomposition consisting of 42...Figure 3.6 Rectangular decomposition. Rectangular decomposition (consisting ...Figure 3.7 Triangular decomposition with regions of interest. Triangular par...Figure 3.8 Comparison of cell decomposition approaches. Cell decompositions ...Figure 3.9 Comparison of cell decomposition approaches. Criteria for compari...Figure 3.10 Comparison of cell decomposition approaches. Percentage of small...

4 Chapter 4Figure 4.1 An example of a discretized environment. A discretized environmen...Figure 4.2 Graph abstraction of an environment. Graph abstraction of the dis...Figure 4.3 Example of a transition system model of a robot. Transition syste...Figure 4.4 Example of a Petri net model of a team of robots. Petri net model...Figure 4.5 Spurious markings in a Petri net system. A small Petri net system...Figure 4.6 Example of a discretized environment and two robots. A discretize...Figure 4.7 Example of an RAS PN model. The RAS PN model of two robots evolvi...Figure 4.8 Examples of Büchi automata corresponding to the LTL formulas give...Figure 4.9 Reduced Büchi automaton. Büchi automaton form of Figure 4.8(d) ...

5 Chapter 5Figure 5.1 Path planning using a search on a graph (example generated by usi...Figure 5.2 Number of cells to be traversed versus number of obstacles and gr...Figure 5.3 Computation time for finding waypoints by optimizations (2) to (4...Figure 5.4 Relative increment in length of the obtained trajectory for weigh...Figure 5.5 Relative increment in length of the obtained trajectory for weigh...Figure 5.6 Relative increment in length of the obtained trajectory for waypo...Figure 5.7 Environment used in Example 5.2. If is too small and the termin...Figure 5.8 Environment of size . Simulation with a receding horizon strateg...Figure 5.9 Simulation with a receding horizon strategy ( and ). Resulting ...Figure 5.10 Scenario with the final point (blue star on the right) not place...Figure 5.11 Example of a product automaton between the transition system f...Figure 5.12 A simple environment surrounded by a depot region. A simple envi...Figure 5.13 A more complex environment surrounded by a depot region. A more ...