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

Library of Congress Cataloging‐in‐Publication Data is available.

Hardback: 9781119486329

To our families

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 2introduces 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 5presents 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 6based 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 6presents 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: zhou@njit.edu

Website: http://web.njit.edu/zhou

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.