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, Spain
Ramó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
AGVAutomated Guided VehicleCNFConjunctive Normal FormCPUCentral Processing UnitCTLComputation Tree LogicDNFDisjunctive Normal FormFSAFinite State AutomataGUIGraphical User InterfaceGVDGeneralized Voronoi DiagramICRInstantaneous Centre of RotationLTLLinear Temporal LogicMILPMixed‐Integer Linear ProgrammingMPCModel Predictive ControlODEOpen Dynamics EnginePIProportional IntegralPIDProportional Integral DerivativePNPetri NetPRMProbabilistic Road MapRARMPNResource Allocation Robot Motion Petri NetRASResource Allocation SystemRMPNRobot Motion Petri NetRMToolRobot Motion ToolboxRRTRapidly exploring Random TreeV‐GraphVisibility Graph
Chapter 1 Introduction
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