Robot Path Planning and Cooperation | springerprofessional.de

Springer Professional

Top

2018 | Book

Read chapter Read first chapter

Robot Path Planning and Cooperation

Foundations, Algorithms and Experimentations

Authors: Dr. Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Publisher: Springer International Publishing

Book Series : Studies in Computational Intelligence

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access

About this book

This book presents extensive research on two main problems in robotics: the path planning problem and the multi-robot task allocation problem. It is the first book to provide a comprehensive solution for using these techniques in large-scale environments containing randomly scattered obstacles. The research conducted resulted in tangible results both in theory and in practice. For path planning, new algorithms for large-scale problems are devised and implemented and integrated into the Robot Operating System (ROS). The book also discusses the parallelism advantage of cloud computing techniques to solve the path planning problem, and, for multi-robot task allocation, it addresses the task assignment problem and the multiple traveling salesman problem for mobile robots applications. In addition, four new algorithms have been devised to investigate the cooperation issues with extensive simulations and comparative performance evaluation. The algorithms are implemented and simulated in MATLAB and Webots.

Advertisement

Table of Contents

Frontmatter

Global Robot Path Planning

Frontmatter

Chapter 1. Introduction to Mobile Robot Path Planning

Abstract

Robotic is now gaining a lot of space in our daily life and in several areas in modern industry automation and cyber-physical applications. This requires embedding intelligence into these robots for ensuring (near)-optimal solutions to task execution. Thus, a lot of research problems that pertain to robotic applications have arisen such as planning (path, motion, and mission), task allocation problems, navigation, tracking. In this chapter, we focused on the path planning research problem.

Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Chapter 2. Background on Artificial Intelligence Algorithms for Global Path Planning

Abstract

In the literature, numerous path planning algorithms have been proposed. Although the objective of these algorithms is to find the shortest path between two positions A and B in a particular environment, there are several algorithms based on a diversity of approaches to find a solution to this problem. The complexity of algorithms depends on the underlying techniques and on other external parameters, including the accuracy of the map and the number of obstacles. It is impossible to enumerate all these approaches in this chapter, but we will shed the light on the most used approaches in the literature.

Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Chapter 3. Design and Evaluation of Intelligent Global Path Planning Algorithms

Abstract

Global path planning is a crucial component for robot navigation in map-based environments. It consists in finding the shortest path between start and goal locations. The analysis of existing literature in Chap. 2 shows two main approaches commonly used to address the path planning problem: (1) exact methods and (2) heuristic methods. A* and Dijkstra are known to be the most widely used exact methods for mobile robot global path planning. On the other hand, several heuristic methods based on ant colony optimization (ACO), genetic algorithms (GA), Tabu Search (TS), and hybrid approaches of both have been proposed in the literature. One might wonder which of these methods is more effective for the robot path planning problem. Several questions also arise: Do exact methods consistently outperform heuristic methods? If so, why? Is it possible to devise more powerful hybrid approaches using the advantages of exact and heuristics methods? To the best of our knowledge, there is no comprehensive comparison between exact and heuristic methods in solving the path planning problem. This chapter fills the gap, addresses the aforementioned research questions, and proposes a comprehensive simulation study of exact and heuristic global path planners to identify the more appropriate technique for the global path planning.

Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Chapter 4. Integration of Global Path Planners in ROS

Abstract

Global path planning consists in finding a path between two locations in a global map. It is a crucial component for any map-based robot navigation. The navigation stack of the Robot Operating System (ROS) open-source middleware incorporates both global and local path planners to support ROS-enabled robot navigation. Only two basic algorithms are defined for the global path planner including Dijkstra and carrot planners. However, more intelligent global planners have been defined in the literature but were not integrated in ROS distributions. The contribution of this work consists in integrating the \(RA^{*}\) path planner, defined in Chap. 3, into the ROS global path planning component as a plugin. We demonstrate how to integrate new planner into ROS and present their benefits. Extensive experimentations are performed on simulated and real robots to show the effectiveness of the newly integrated planner as compared to ROS default planner.

Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Chapter 5. Robot Path Planning Using Cloud Computing for Large Grid Maps

Abstract

As discussed in Chap. 3, \(A^{*}\) algorithm and its variants are the main mechanisms used for grid path planning. On the other hand, with the emergence of cloud robotics, recent studies have proposed to offload heavy computation from robots to the cloud, to save robot energy and leverage abundant storage and computing resources in the cloud. In this chapter, we investigate the benefits of offloading path planning algorithms to be executed in the cloud rather than in the robot. The contribution consists in developing a vertex-centric implementation of the \(RA^{*}\), a version of \(A^{*}\) that we developed for grid maps and that was proven to be much faster than \(A^{*}\) (refer to Chap. 3), using the distributed graph processing framework Giraph that rely on Hadoop. We also developed a centralized cloud-based C++ implementation of the algorithm for benchmarking and comparison purposes.

Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Multi-robot Task Allocation

Frontmatter

Chapter 6. General Background on Multi-robot Task Allocation

Abstract

Multi-robot systems (MRSss) face several challenges, but the most typical problem is the multi-robot tasks allocation (MRTA). It consists in finding the efficient allocation mechanism in order to assign different tasks to the set of available robots. Toward this objective, robots will work as cooperative agents. MRTA aims at ensuring an efficient execution of tasks under consideration and thus minimizing the overall system cost. Various research works have solved the MRTA problem using the multiple traveling salesman problem (MTSP) formulation. In this context, an overview on MRTA and MTSP is given in this chapter. Furthermore, a summary of the related works is presented.

Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Chapter 7. Different Approaches to Solve the MRTA Problem

Abstract

The multi-robot task allocation problem is a fundamental problem in robotics research area. The problem roughly consists of finding an optimal allocation of tasks among several robots to reduce the mission cost to a minimum. As mentioned in Chap. 6, extensive research has been conducted in the area for answering the following question: Which robot should execute which task? In this chapter, we design different solutions to solve the MRTA problem. We propose four different approaches: an improved distributed market-based approach (IDMB), a clustering market-based approach (CM-MTSP), a fuzzy logic-based approach (FL-MTSP), and Move-and-Improve approach. These approaches must define how tasks are assigned to the robots. The IDBM, CM-MTSP, and Move-and-Improve approaches are based on the use of an auction process where bids are used to evaluate the assignment. The FL-MTSP is based on the use of the fuzzy logic algebra to combine objectives to be optimized.

Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Chapter 8. Performance Analysis of the MRTA Approaches for Autonomous Mobile Robot

Abstract

The multi-robot task allocation is a fundamental problem in robotics research area. Indeed, robots are typically intended to collaborate together to achieve a given goal. This chapter studies the performance of the IDBM, CM-MTSP, FL-MTSP, and Move-and-Improve approaches. In order to highlight the performance of the proposed schemes, we compared each one to appropriate existing ones. IDMB was compared with the RTMA [1], CM-MTSP was compared with single-objective and greedy algorithms, and FL-MTSP was compared with a centralized approach based on genetic algorithm and with NSGA-II algorithm. To validate the efficiency of the Move-and-Improve distributed algorithm, we first conducted extensive simulations and evaluated its performance in terms of the total traveled distance and the ratio of overlaped targets under different settings. The simulation results show that IDMB and Move-and-Improve algorithms produce near-optimal solutions. Also, CM-MTSP and FL-MTSP provide a good trade-off between conflicting objectives.

Anis Koubaa, Hachemi Bennaceur, Imen Chaari, Sahar Trigui, Adel Ammar, Mohamed-Foued Sriti, Maram Alajlan, Omar Cheikhrouhou, Yasir Javed

Backmatter

Title: Robot Path Planning and Cooperation
Authors: Dr. Anis Koubaa
Hachemi Bennaceur
Imen Chaari
Sahar Trigui
Adel Ammar
Mohamed-Foued Sriti
Maram Alajlan
Omar Cheikhrouhou
Yasir Javed
Copyright Year: 2018
Publisher: Springer International Publishing
Electronic ISBN: 978-3-319-77042-0
Print ISBN: 978-3-319-77040-6
DOI: https://doi.org/10.1007/978-3-319-77042-0

Premium Partner