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 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