Path Planning of Cooperative Mobile Robots Using Discrete Event Models

Оглавление

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

Table of Contents

List of Tables

List of Illustrations

Guide

Pages

Path Planning of Cooperative Mobile Robots Using Discrete Event Models

Foreword

Preface

Acknowledgments

Acronyms

Chapter 1 Introduction. 1.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

Notes

2 Robot Motion Toolbox. 2.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.5.1 Pure pursuit algorithm

2.5.2 PI controller

2.6 Illustrative examples. 2.6.1 Examples about path planning aspects

2.6.2 Examples about motion control aspects

2.6.3 Examples about multi‐robot systems and high‐level tasks

2.7 Conclusions

Note

3 Cell Decomposition Algorithms. 3.1 Introduction

3.2 Cell decomposition algorithms

3.2.1 Hypothesis

3.2.2 Trapezoidal decomposition

Algorithm 3.1: Trapezoidal decomposition

3.2.3 Triangular decomposition

Algorithm 3.2: Triangular decomposition - interface with Matlab's function

3.2.4 Polytopal decomposition

Algorithm 3.3: Polytopal decomposition

3.2.5 Rectangular decomposition

Algorithm 3.4: Procedure check_split_rectangle

3.3 Implementation and extensions

3.3.1 Extensions

3.3.2 Implemented functions

3.4 Comparative analysis

3.4.1 Qualitative comparison

3.4.2 Quantitative comparison

3.5 Conclusions

Note

4 Discrete Event System Models. 4.1 Introduction

4.2 Environment abstraction

Definition 4.1

4.3 Transition system models

4.3.1 Single robot case

Definition 4.2

Algorithm 4.1: Construct the transition system TS

4.3.2 Multi‐robot case

Definition 4.3

4.4 Petri net models

Definition 4.4

Example 4.1

Example 4.2

Algorithm 4.2: Construct the RMPN system Q

4.5 Petri nets in resource allocation systems models

Remark 4.1

Definition 4.5

Definition 4.6

4.6 High‐level specifications

Algorithm 4.3: Obtain the RARMPN model for capacity constraints

4.7 Linear temporal logic

Definition 4.7

Definition 4.8

Example 4.3

Definition 4.9

Definition 4.10

Example 4.4

Algorithm 4.4: Update the Büchi automaton B

4.8 Conclusions

Notes

5 Path Planning by Using Transition System Models

5.1 Introduction

5.2 Two‐step planning for a single robot and reachability specification

Example 5.1

5.3 Quantitative comparison of two‐step approaches

5.4 Receding horizon approach for a single robot and reachability specification

Example 5.2

Algorithm 5.1: Path planning optimizing the waypoints

5.5 Simulations and analysis

5.6 Path planning with an specification

Definition 5.1

Algorithm 5.2: Find a path of TS satisfying an LTL formula

Example 5.3

5.7 Collision avoidance using initial delay. 5.7.1 Problem description

Example 5.4

Problem 5.1 (Decentralized)

Problem 5.2 (Centralized)

Remark 5.1

Example 5.5

5.7.2 Solution for Problem 5.1 (decentralized)

Example 5.6

5.7.3 Solution for Problem 5.2 (centralized)

Example 5.7

5.8 Conclusions

Note

6 Path and Task Planning Using Petri Net Models. 6.1 Introduction

6.2 Boolean‐based specifications for cooperative robots

6.2.1 Problem definition and notations

6.2.2 Linear restrictions for Boolean‐based specifications. Definition 6.1

6.2.3 Solution for constraints on the final state

Lemma 6.1

Algorithm 6.1: Iterative construction of agent strategies

6.2.4 Solution for constraints on trajectory and final state

Remark 6.1

Remark 6.2

6.2.5 Discussion on the above solutions

6.2.6 Suboptimal solution

Algorithm 6.2: Reduce the RMPN model by joining places with the same output

6.2.7 Simulation examples

6.3 LTL specifications for cooperative robots. 6.3.1 Problem definition and solution

Algorithm 6.3: Construct set Γ of accepted runs

Example 6.1

Algorithm 6.4: Constraints for the set S

Example 6.2

Algorithm 6.5: Check if σ returned by MILP (6.11) is applicable

Algorithm 6.6: Iterative construction of solution

6.3.2 Simulation examples

6.4 A sequencing problem. 6.4.1 Problem statement

6.4.2 Solution

Proposition 6.1

Remark 6.3

Algorithm 6.7:

6.5 Task gathering problem

6.5.1 Problem formulation

Example 6.3

6.5.2 Solution

Algorithm 6.8: Iterative construction of agent strategies for task gathering problem

Example 6.4

6.6 Deadlock prevention using resource allocation models

Algorithm 6.9: Liveness enforcement

6.7 Conclusions

Notes

7 Concluding Remarks

Bibliography

Index. b

c

d

g

i

l

m

o

p

r

s

t

IEEE PRESS SERIESONSYSTEMSSCIENCE AND ENGINEERING

WILEY END USER LICENSE AGREEMENT

Отрывок из книги

IEEE Press 445 Hoes Lane Piscataway, NJ 08854

.....

Figure 1.5 Motion control methods. Main categories for motion control in mobile robotics and an example of some well‐known methods for each of them.

where is the error between the actual position of the robot and the desired target position. Notice that Eq. (1.1) defines a quasi‐zero error because in some situations, for instance considering uncertainty, an exact error equal to zero cannot be achieved [81]. The control problem associated with a mobile robot can then be defined as a feedback control system. The idea is that the controller senses the position/pose of the robot, compares it against the desired reference, computes corrective actions based on a model of the robot and actuates the robot to effect the desired change. As highlighted in [9], the key issues in designing control logic are ensuring that the dynamics of the closed‐loop system are stable (bounded disturbances give bounded errors) and that they have additional desired behavior (good disturbance attenuation and fast responsiveness to changes in the operating point, among others).

.....