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 Professor
Fellow of IEEE, AAAS, IFAC, and CAA
Founding Editor, IEEE Press–Wiley Book Series on Systems Science and Engineering
Email: [email protected]
Website: 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, Spain
Cristian Mahulea
Iasi, Romania
Marius Kloetzer
Almeria,
