106,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Wissenschaft und neue Technologien
- Serie: IEEE Series on Systems Science and Engineering
- Sprache: Englisch
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.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 351
Veröffentlichungsjahr: 2020
Ähnliche
Table of Contents
Cover
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
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.6 Illustrative examples
2.7 Conclusions
3 Cell Decomposition Algorithms
3.1 Introduction
3.2 Cell decomposition algorithms
3.3 Implementation and extensions
3.4 Comparative analysis
3.5 Conclusions
4 Discrete Event System Models
4.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
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
6 Path and Task Planning Using Petri Net Models
6.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
7 Concluding Remarks
Bibliography
Index
IEEE PRESS SERIESONSYSTEMSSCIENCE AND ENGINEERING
End User License Agreement
List of Tables
Chapter 3
Table 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...
Chapter 4
Table 4.1 Comparison between the discrete formalisms used in multi‐robot path...
Table 4.2 Constants, Boolean and temporal operators used to define
formulas....
Chapter 5
Table 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...
List of Illustrations
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.
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...
Chapter 3
Figure 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...
Chapter 4
Figure 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) ...
Chapter 5
Figure 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 ...
Chapter 6
Figure 6.1 An example of a Boolean specification. The robots are required to...
Figure 6.2 Random environment with ten regions of interest and seven robots ...
Figure 6.3 Random environment with seven regions of interest and five robots...
Figure 6.4 Büchi automaton for the LTL specification
The inputs that enabl...
Figure 6.5 Trajectories computed for the LTL specification
The robots sync...
Figure 6.6 Trajectories computed for the LTL specification
Other trajector...
Figure 6.7 A simple environment to illustrate the sequencing problem. An env...
Figure 6.8 RMPN for the team in the environment illustrated in Figure 6.7. T...
Figure 6.9 A simple environment to illustrate the task gathering problem. An...
Figure 6.10 Environment with three regions of interest sketched using RMTool...
Figure 6.11 Example of a RARMPN model. The RARMPN model of two robots evolvi...
Figure 6.12 Example of a RARMPN model with a monitor place
. The RARMPN mod...
Guide
Cover
Table of Contents
Begin Reading
Pages
ii
iii
iv
v
xi
xii
xiii
xv
xvi
xvii
xix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
b1
b2
213
IEEE Press445 Hoes LanePiscataway, NJ 08854
IEEE Press Editorial BoardEkram Hossain, Editor in Chief
David Alan Grier
Andreas Molisch
Diomidis Spinellis
Donald Heirman
Saeid Nahavandi
Sarah Spurgeon
Elya B. Joffe
Ray Perez
Ahmet Murat Tekalp
Xiaoou Li
Jeffrey Reed
Path Planning of Cooperative Mobile Robots Using Discrete Event Models
Cristian Mahulea
University of Zaragoza, Spain
Marius Kloetzer
“Gheorghe Asachi” Technical University of Iasi, Romania
Ramón González
Robonity, Spain
© 2020 by The Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Published by John Wiley & Sons, Inc., Hoboken, New Jersey.Published simultaneously in Canada.
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per‐copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750‐8400, fax (978) 750‐4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748‐6011, fax (201) 748‐6008, or online at http://www.wiley.com/go/permissions.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762‐2974, outside the United States at (317) 572‐3993 or fax (317) 572‐4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging‐in‐Publication Data is available.
Hardback: 9781119486329
To our families
Foreword
The path planning approach based on Discrete Event System (DES) models is an important – but a challenging – problem. It has been studied for a number of years in the DES community in the field of automated guided vehicle (AGV) systems. In this case, the main issue is to compute collision‐free paths for an AGV from a starting configuration to a goal one. For multi‐agent systems, an additional problem is to avoid deadlocks that could result if waiting modes are introduced. The main solutions obtained are based on the results of deadlock prevention and avoidance from Resource Allocation Systems that allow one to use a DES structure to obtain deadlock‐free trajectories of AGVs. Even if the complexity of these approaches is high, researchers have identified some computationally tractable solutions for some particular classes.
This book is a step forward from the classical AGV navigation problem, by assuming high‐level specifications for a team of cooperative robots. Therefore, the problem is not to reach only some goal configurations, but to accomplish a more complicated task combining logic and temporal operators on some regions of the environment, called regions of interest. This problem appeared some years ago in the formal method community, where so‐called symbolic approaches are used to solve it. Mainly, its solution consists in obtaining a model for a robot team and a model for specifications, combining them in a smart way and then computing robot trajectories. Initially, the model of the team is obtained by using transition systems that, in the case of teams with more than 2 or 3 robots, suffer from a so‐called state space explosion problem, i.e. the number of discrete states grows exponentially with the number of robots, making this approach impractical.
In order to avoid this state space explosion problem, two alternative approaches have been proposed. One approach consists in dividing a high‐level specification into (local) subformulas that can be executed in parallel, and then, for each local formula, a special model is constructed allowing distribution of the fulfillment of the task among robots. Another approach, which is presented in this book, tackles the state explosion problem by using Petri net models and optimization techniques, thus avoiding a formula from being divided and, hence, allowing more general specifications than language subclasses.
This book presents an open‐source Matlab toolbox called Robot Motion Toolbox (RMTool), which can be freely downloaded and used to check all the presented approaches. Chapter 2 introduces this toolbox and focuses on its usage in introductory courses of robotics. All the examples in the following chapters are illustrated by using this toolbox. A reader can repeat them easily.
DES models can be mainly constructed by using two approaches: cell decomposition of an environment and sample‐based methods. This book is focused on the former as presented in Chapter 3. It allows one to obtain a DES model for a team of robots. The main advantage of this approach over the sample‐based one is the fact that it always returns a solution in finite time as long as this solution exists. The formal description of the necessary DES models is given in Chapter 4, together with the high‐level specifications to be used: Linear Temporal Logic,and Boolean‐based formulas.
For completeness, this book also presents the transition system models and methods. Chapter 5 presents some results related to this type of model that basically consists in computing the synchronous product of different transition systems in order to obtain the model of a team of robots. Some new techniques for computing trajectories are also presented, as for example one based on Model Predictive Control. Furthermore, it describes a method to avoid collisions by introducing initial delays to some trajectories.
One of the main novelties of the book is the approaches described in Chapter 6 based on Petri net models, which are defined in Chapter 4. These approaches try to avoid the construction of the synchronous product of automata. However, an additional problem appears and is related to obtaining the sequence of firing transitions. The optimization problems used for path planning return firing vectors, but, in the current case, firing sequences are necessary to obtain robot moving sequences. In general, this is a very complicated problem in the Petri net literature. However, based on the particular structure of a Petri net, an algorithm is provided to compute the firing sequence in polynomial time. Additionally, Chapter 6 presents some particular problems related to the collections of some tasks and discusses further approaches for deadlock prevention.
This book opens a number of future research directions and can be of particular interest in two different communities. First, for the Discrete Event System community, it opens an interesting application area of being possible to apply the results from this community to a particular application. Second, for the robotic community, it can use the theoretical results from a different community to solve particular problems. Hence, this book should certainly become a very important addition to the IEEE Press–Wiley Book Series on Systems Science and Engineering.
MengChu Zhou, PhD and Distinguished ProfessorFellow of IEEE, AAAS, IFAC, and CAAFounding Editor, IEEE Press–Wiley Book Series on Systems Science and EngineeringEmail: [email protected]: http://web.njit.edu/zhou
Preface
Mobile robotics comprises a successful field in the world today. It is not strange to see little mobile robots cleaning our house, or big robots moving goods in factories, harbors or airports, or even adventurous mobile robots exploring other worlds.
One common issue to all those robots deals with the problem of generating feasible paths or routes between a given starting position and a goal or target position while avoiding (static) obstacles. This problem is addressed within the area of path planning. Due to the importance of this problem in robot navigation, path planning has received considerable attention and numerous strategies have been proposed.
When a group of robots work within the same environment and cooperate in order to accomplish a high‐level task given as a high‐level specification, standard path planning algorithms employed by the robotics community, based on potential functions or road maps, may lead to wrong or even unfeasible results.
This book formulates the problem of path planning of cooperative mobile robots by using the paradigm of discrete‐event systems. First, a high‐level specification is expressed in terms of a Boolean or Linear Temporal Logic (LTL). The environment is then divided into discrete regions of a chosen geometrical shape by using cell decomposition. This book compares the performance of several cell decomposition algorithms in terms of several metrics. This decomposition can be used to define a discrete event system (DES) modeling the movement capabilities of the robot or of the team by using Transition System or Petri Net models. The obtained DES is next combined with the model of the high‐level specification to be accomplished by the group of robots. Finally, the resulting model is used to compute the trajectories via a graph search algorithm or solving optimization problems.
This book contributes an interactive software tool that the intended user can exploit in order to simulate and test all the strategies introduced and formulated in the book. This software tool, called RMTool (Robot Motion Toolbox), is freely available online and can be run in Matlab. It can be used for teaching mobile robotics in introductory courses, as the user can interact with the tool by using a Graphical User Interface (GUI), without requiring previous knowledge of Matlab.
This book is primarily aimed at undergraduate and graduate students and college and university professors in the areas of robotics, artificial intelligence, systems modeling, and autonomous control. The topics addressed in this book can also be welcomed by researchers, PhD students, and postgraduate students with a focus on robot motion planning, centralized robot planning solutions for teams of robots, and interactive teaching tools to be used in engineering courses. The contents of this book and the accompanying software tool can be employed by students and professors at the high‐school level with a previous background in mathematics and engineering.
Zaragoza, SpainCristian Mahulea
Iasi, RomaniaMarius Kloetzer
Almeria, SpainRamón González
Acknowledgments
The authors would like to express their sincere appreciation to all their collaborators, especially to the following professors and researchers (in alphabetic order) who co‐authored some works that further led to the results included in this book: Calin Belta, Adrian Burlacu, Yushan Chen, José‐Manuel Colom, Xu Chu Ding, Narcis Ghita, Karl Iagnemma, Doru Panescu, Luis Parrilla, Octavian Pastravanu, Manuel Silva, Emanuele Vitolo, and Xu Wang. Many thanks to Professor MengChu Zhou for the invitation to write this book for the IEEE Press–Wiley Book Series on Systems Science and Engineering.
Furthermore, our thanks go to the institutions that offered support for performing the research on which this book is based: Aragón Institute on Engineering Research (I3A) and Department of Computer Science and Systems Engineering, University of Zaragoza, Spain; Faculty of Automatic Control and Computer Engineering, Technical University of Iasi, Romania; Robonity: innovation driven startup, Spain; Center for Information and Systems Engineering, Boston University, USA; Massachusetts Institute of Technology, USA.
The authors also acknowledge the financial support of the following grants from the last few years. In Spain: MINECO‐FEDER DPI2014‐57252‐R project, University of Zaragoza UZ2018‐TEC‐06 and JIUZ‐2018‐TEC‐10 projects and CEI Iberus Mobility Grants 2014 funded by the Ministry of Education of Spain within the Campus of Excellence International Program; in Romania: CNCS‐UEFISCDI project PN‐III‐P1‐1.1‐TE‐2016‐0737, CNCSIS‐UEFISCSU project PN‐IIRU‐PD‐333/2010; in China: NSFC Grant No. 6155011023.
We express our thanks to those who read the initial version of this book and formulated useful suggestions, namely the anonymous reviewers and our colleagues Eduardo Montijano and Sofia Hustiu. Last but not least, the authors are most grateful to their families for all their love, encouragement, and support.
Acronyms
AGV
Automated Guided Vehicle
CNF
Conjunctive Normal Form
CPU
Central Processing Unit
CTL
Computation Tree Logic
DNF
Disjunctive Normal Form
FSA
Finite State Automata
GUI
Graphical User Interface
GVD
Generalized Voronoi Diagram
ICR
Instantaneous Centre of Rotation
LTL
Linear Temporal Logic
MILP
Mixed‐Integer Linear Programming
MPC
Model Predictive Control
ODE
Open Dynamics Engine
PI
Proportional Integral
PID
Proportional Integral Derivative
PN
Petri Net
PRM
Probabilistic Road Map
RARMPN
Resource Allocation Robot Motion Petri Net
RAS
Resource Allocation System
RMPN
Robot Motion Petri Net
RMTool
Robot Motion Toolbox
RRT
Rapidly exploring Random Tree
V‐Graph
Visibility Graph
Chapter 1Introduction
1.1 Historical perspective of mobile robotics
Since its first application in the 1940s, robot arms or manipulators have demonstrated a great success in the world of industrial manufacturing. These robot arms can perform repetitive tasks such as spot welding, painting, machine loading and unloading, electronic assembly, packaging, and palletizing, among other activities. However, industrial robots lack of one fundamental property: mobility. The fixed‐base manipulator has a limited range of motion that depends on where it is bolted down. The ability to move is what makes a mobile robot travel freely throughout a given environment. However, this mobility advantage can also be its doom if the robot does not account for a reliable navigation strategy.
One navigation approach is to just react to what is sensed; this is called reactive navigation [7, 186, 193]. For example, the robotic tortoise Elsie, built in the 1940s by the Edison‐Swan Electric Company, reacted to her environment and could seek out a light source without having any explicit plan or knowledge of the position for the light, see Figure 1.1a. This reactive navigation strategy is exploited today by Automated Guided Vehicles (AGVs) in many factories [6, 144]. For example, Amazon uses AGVs in more than ten of its warehouses located in the US. These robots were developed by the company Kiva, later acquired by Amazon in 2012 and becoming AmazonRobotics (https://www.amazonrobotics.com).
Reactive systems can be fast and simple when sensing is connected directly to action, that is, there is no need for resources to hold and maintain a representation of the world nor any capability to reason about that representation [41]. However, such reactive navigation requires a fixed infrastructure where the robot is going to move, for example, a painted line on the floor, a buried cable that emits radio‐frequency signals, or wall‐mounted bar codes. The second major drawback of this approach is that it limits the mobility of the robot to those areas where the guidance system is located or installed; this explains why AGV are usually applied in factories.
Figure 1.1 Mobile robots and reactive navigation. Example of mobile robots based on reactive navigation strategies.
With the explosion of digital technology in the 1970s, a group of engineers working at the Stanford Research Institute (SRI) developed the first mobile robot to be operated using autonomous reasoning [159]. The robot Shakey was capable of 3D perception and created a map of its environment and then reasoned about the map to plan a path to its destination, see Figure 1.2a. An optical rangefinder and a vidicon television camera with controllable focus and iris were mounted on a tilt platform for sensing. Offboard communication was provided via two radio channels: one for video and the other providing command and control. This ability to make maps and reason about them made Shakey capable of performing more complex tasks than former robots based on reactive navigation strategies. After Shakey, the next big step in the field of mobile robotics came from the Robotics Institute at Carnegie Mellon University in the 1980s [28]. The Terregator robot (Terrestrial Navigator) was designed to operate autonomously in outdoor scenarios, see Figure 1.2b. It was a six‐wheeled skid‐steer robot utilizing compliant tires for suspension. Terregator subsystems included locomotion, power, computation, controls, wireless telemetry (serial links and two channels of UHF video), orientation sensors, and navigation payloads. The robot's onboard control system consisted of a central processing unit (CPU) linked to motor controllers. This CPU calculated the robot's position and orientation from a gyroscope, wheel encoders, and inclinometers (dead‐reckoning). Additionally, this system was also responsible for guiding the robot to a commanded destination provided by an offboard supervisor (remote command station). This supervisor made use of the images coming from the video camera mounted on the vehicle. Terregator was even used for mapping a portion of a mine thanks to its path planning and mapping capabilities [28]. Another big milestone in the early ages of mobile robotics came from the University of Munich in Germany. Several vehicles developed by Prof. Ernst Dickmanns, e.g. Daimler‐Benz VITA‐2 and UniBwM VaMP, drove autonomously on European highways at speeds up to 130 km/h, see Figure 1.2c. This astonishing leap was achieved by using a visual feedback control system that tracked the road boundaries. This advanced control system ran in a multiprocessor image processing system using contour correlation and curvature models together with the laws of perspective projection [52]. The vehicle's position was estimated relative to the driving lane and road curvature by means of a Kalman filter. In 1994, the VaMP driverless car designed by Prof. Dickmanns drove 1600 kilometers, of which 95% were driven autonomously [51].
Figure 1.2 Autonomous mobile robots. Example of pioneering autonomous mobile robots.
These pioneering mobile robots opened the door to the significant achievements in the field of mobile robotics during the last twenty years. Today, mobile robots have explored other worlds such as Mars or the Moon, e.g. MER rovers and MSL rover [87, 194; mobile robots have worked at Antarctica seeking meteorites, e.g. Nomad robot [5; robots are able to clean our houses, e.g. iRobot Roomba; to perform harvesting activities in agriculture, e.g. ASI autonomous tractor; and they are also present in our schools, like the SoftBank Robotics NAO humanoid robot.
1.2 Path planning. Definition and historical background
A fundamental task for any mobile robot is its ability to plan collision‐free trajectories from a start to a goal position or visiting a series of positions, i.e. regions of interest, among a collection of (static) obstacles. This is the robot's cognitive level. Cognition generally represents the purposeful decision‐making and execution that a system utilizes to achieve its highest‐order goals. Given a map and a goal position (or a list of high‐level goals), path planning involves identifying a trajectory that will cause the robot to reach the goal position (a 2D point) or pose (a 2D point and an orientation) when executed [35, 135, 191]. It bears mentioning that position refers to the longitudinal and lateral coordinates in a Cartesian frame. Pose also considers the orientation.
Path planning comprises the highest level within a typical navigation architecture of a mobile robot. As observed in Figure 1.3, there are four big modules or layers. The second layer in this navigation architecture includes the motion controller (or trajectory following strategy), which is responsible for generating the control actions in such a way that the robot follows as accurately as possible the reference trajectory provided by the path planning layer. These control actions will be determined according to the error between the current robot's position and the next desired waypoint. The third layer deals with the low‐level PID controllers that ensure that the control actions generated by the motion controller are reached by the robot actuators, i.e. wheel motors. As explained before, it is crucial for the motion controller to know the current position of the robot; this is calculated by the last layer in the robot's navigation architecture: the localization layer. Here, a set of sensors are employed to get the robot's position as accurately as possible. Another significant observation about this traditional navigation architecture is that the execution time or the sampling time of each layer is different. For example, the time to get a response from the path planning layer is on the order of minutes or seconds, the time for the motion control layer is on the order of seconds or hundreds of milliseconds, and the fastest layer comprises the low‐level controllers that run on the order of milliseconds.
Figure 1.3 Navigation architecture of a mobile robot. Example of a navigation architecture of a mobile robot (University of Almeria's Fitorobot robot) [78].
The history of robot path planning began with the early computer‐controlled robots, i.e. SRI Shakey robot. One of the pioneering references in this field is the book “Robot Motion Planning” authored by Jean‐Claude Latombe in 1980 [132],1. At that time, the most advanced planners were barely able to compute collision‐free paths for objects moving in planar workspaces. In the 1990s, researchers working in this field faced another challenge: planning motions in the presence of kinematic constraints like non‐holonomic robot systems2, e.g. a car that cannot rotate around its axis without also changing its position [133]. At the beginning of the twenty‐first century, robot planners could be applied to robots with many degrees of freedom in complex environments, coordinate multiple robots, and handling dynamic environments. In 2005 and 2006 other key references appeared in the field of mobile robotics: “Principles of Robot Motion: Theory, Algorithms, and Implementations” by Choset et al. [35] and “Planning Algorithms” by Stephen LaValle [135]. These books opened the door to multiple milestones in this field, as roadmaps, cell decomposition methods, and sampling‐based planning algorithms.
Traditional planning algorithms, sometimes called combinatorial or exact algorithms, build discrete representations of a given environment, i.e. a map, without losing any information. Some of them are complete, which means that they must find a solution if one exists; otherwise, they report failure [135]. On the contrary, sampling‐based solutions sparsely sample the world map and conduct discrete searches that utilize these samples. This paradigm sacrifices completeness with the benefit of a faster computation [135].
As Figure 1.4 shows, there are two big areas in the field of path planning in mobile robotics: combinatorial or exact algorithms and sampling‐based planning. This book focuses on the first category, but the second category is also described for completeness purposes. Notice that the area of reactive navigation has also been included here for completeness purposes. Recall that the main difference between path planning approaches and reactive navigation is that in the first case a map of the environment is needed.
The first category, exact algorithms, can be divided into two areas: road map planning and cell decomposition. The road map planning approaches capture the connectivity of the robot's free space in a network of 2D curves or lines, called road maps. Once a road map is constructed, it is used as a network of road segments. At this point, path planning is reduced to connecting the initial and goal position of the robot to the road network and then searching for a series of roads from the initial robot position to its goal position [191]. To this category belong two well‐known methods in the field of mobile robotics: visibility graph and Voronoi diagram.
The visibility graph (or V‐graph), formally described by Lozano‐Perez and Wesley in the 1970s [142], represents a complete and easy to implement algorithm. This algorithm is based on constructing an undirected graph where edges come as close as possible to obstacles, then resulting in minimum‐length paths. An important aspect is that obstacles can be inflated in order to avoid an incident where the robot could pass by too close to them, which could lead to collisions [58]. The main drawbacks of this algorithm are that it can demand a high computation time for getting a trajectory in environments with complicated obstacles, and some points of the path are too close to obstacles if inflation is not used. The fast dynamic visibility graph (DVG) approach proposed in [100] represents an efficient implementation of the traditional V‐graph. The V‐graph has been largely used by the robotics community from Shakey in the 1970s to recent publications like [39], where the V‐graph algorithm is used to find the obstacle‐free path after processing digital images acquired by a camera onboard a mobile robot.
The Voronoi diagram was proposed by G.F. Voronoi at the end of the nineteenth century and since then it has been widely used in many areas such as: mathematics, physics, astronomy, geographical information systems, computer graphics, image processing, and robotics. In contrast to the V‐graph approach, a Voronoi diagram tends to maximize the distance between the robot and obstacles in the map, that is, roads stay as far away as possible from obstacles. Therefore, there is no need to inflate the obstacles. As in the V‐graph after the set of roads are determined, a graph search algorithm is applied to estimate the best route between the desired points. An application of the Voronoi diagram in mobile robotics appears in [79]. Here, this algorithm is used by an agricultural robot to move in a greenhouse. There is also a broad field of research combining the advantages of the visibility graph (shortest routes) with those of the Voronoi diagram (maximum distance from the obstacles); see, for example, [151, 211].
Figure 1.4 Path planning methods. Main categories for path planning in mobile robotics and examples of some well‐known methods for each of them.
The second big category comprising exact planning algorithms is cell decomposition. This strategy is based on partitioning the free configuration space into a finite set of regions that can be safely traversed by a robot. Cell decompositions are often employed in high‐level planning approaches where the robot may visit some regions based on logic or temporal requirements (this feature is extended in Section 1.4 and in subsequent chapters).
It bears mentioning that the exact methods further need graph search algorithms in order to finally obtain the optimal route connecting a series of waypoints. For this aspect, three graph search algorithms that return a minimum cost path are usually employed, namely Dijkstra [53], A* [140, 160, 221], and D* [195]. Dijkstra and A* algorithms are great choices for static graphs with positive known arc weights, with A* additionally requiring a heuristic cost function. The D* algorithm, proposed by Anthony Stentz in 1995 [195], constitutes an extension of the classic A* algorithm for graphs, introduced by Nils J. Nilsson in the 1970s [160]. D* considers the 2D map as a cost map where each weight represents the cost of traversing each cell in the horizontal or vertical direction. For cells corresponding to obstacles we can give a huge cost, so D* finds the path minimizing the total cost of travel. This cost may deal with various aspects such as time to drive across a cell, roughness of the terrain, etc. The key feature of D* is that it supports incremental replanning, that is, the algorithm can replan the initial route while the robot discovers that the world is different from the initial plan. The incremental replanning has a lower computational cost than completely replanning, as would be required by A* [41]. The algorithm D* accounts for many successful applications in mobile robotics. For example, in [84], the D* algorithm is used for generating the optimal route for ground autonomous vehicles. More specifically, the cost function associated with the D* algorithm is configured in such a way that the route connecting two points minimizes the uncertainty associated with the elevation of the 3D points in the maps. This route also avoids points where the robot may experience a high risk of entrapment. After the successful introduction of the D* algorithm, there is a recent and broad body of research dealing with extending the features of this algorithm. Some of those recent algorithms are: D* Lite [125], PHI* [57], and E* [169].
Together with combinatorial or exact planning algorithms, another broad body of research in the field of path planning nowadays is related to sampling‐based planning methods. The first algorithm, called Probabilistic Roadmap (PRM), was proposed by Lydia E. Kavraki and Jean‐Claude Latombe in the 1990s [106]. The advantage of PRM is that relatively few points need to be tested to ascertain that the points and the paths between them are obstacle free [41]. The efficacy of several variations of the PRM algorithm is discussed in [75].
A major drawback of PRM is that it assumes that the robot is a point with omnidirectional capabilities. The Rapidly exploring Random Tree (RRT) algorithm takes into account the model of the robot, e.g. differential‐drive motion [134]. However, the main drawback of RRT is that it does not lead to an optimal path. This aspect is overcome by a variant of RRT called RRT*; this algorithm does guarantee the optimality and can find the optimal trajectory when applied to complex non‐holonomic systems [2, 104, 138]. In recent literature, there are numerous RRT‐based strategies trying to ensure optimality despite uncertainty in the motion of the robot [136, 143].
1.3 Motion control. Definition and historical background
The key goal of a mobile robot is to follow the route generated by the path planner, and this goal is responsible for the motion controller. More specifically, robot control deals with the problem of determining the forces (or velocities) that must be developed by the robotic actuators in order for the robot to go to a desired position, track a desired trajectory, and, in general, perform some tasks with desired performance requirements [202].
The control problem can be classified depending on how the reference path is defined: a single target point , a set of waypoints , or a set of poses , where is the time. The time in the previous variables represents a situation where those variables may change along the robot operation. In this sense, the control strategy can be understood as the problem of moving to a point, path following, and trajectory tracking, see Figure 1.5. Notice that, in the trajectory tracking problem the robot orientation must also be controlled, unlike in the other two cases where the final robot orientation depends on the starting position.
Essentially the control problem must ensure
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).
It is important to remark that mobile robotics comprises a challenging field from a control standpoint as there are some phenomena that influence robot's controllability, such as hard constraints fulfillment (e.g. physical limitations of actuators, narrow workspaces), and uncertainties (e.g. unmodelled dynamics, simplified models, noisy measurements). For that reason, in the past few years, many research efforts have been devoted to the application of different control strategies.
One of the first path following approaches was proposed by R. Craig Coulter in the early 1980s for the Terregator robot [45]. The name “pure pursuit” comes from the analogy for the way humans drive. We tend to look some distance in front of the car and head toward that spot. This lookahead distance changes as we drive to reflect the twist of the road and vision occlusions. In the pure pursuit algorithm, this lookahead distance plays a key role between accuracy following the desired route and aggressiveness of the control actions [79
