A Global/Local Path Planner for Multi-Robot Systems with Uncertain Robot Localization
- PDF / 2,369,198 Bytes
- 23 Pages / 595.224 x 790.955 pts Page_size
- 90 Downloads / 269 Views
A Global/Local Path Planner for Multi-Robot Systems with Uncertain Robot Localization ˜ Paulo Lima Silva de Almeida1,2 · Renan Taizo Nakashima2 · Flavio ´ ´ Ramos de Arruda2 ´ Joao Neves-Jr2 · Lucia Valeria Received: 6 February 2019 / Accepted: 31 March 2020 © Springer Nature B.V. 2020
Abstract This paper proposes a path planner for multi-robot systems based on the solution of the multiple traveling salesman problem by genetic algorithm. The main planning goal is to build an efficient path to each robot of the system which jointly ensures that several a priori known points (ways-points) in the environment can be attained by at least one of the robots. During navigation, each robot try to follow its planned path while performing tasks and deviating from unknown static and dynamic obstacles. As the robots have limited sensing and communication skills, their positions can easily become uncertain and the robots will be unable to follow their planned paths. To circumvent this problem, each robot has a local planner, able to recalculate its position and then to resume its planned path. This computation is based on the knowledge about waypoints positions, information exchanged with other robots and a self localization algorithm by triangulation. The proposed global/local path planner is firstly validated by computer simulations. An experimental study is also carried out with a small system with very simple mobile robots with differential drive and Bluetooth communication. The obtained results confirm the efficacy of the proposed path planner. Keywords Multi-robot systems · Path planning · Genetic algorithm · Multiple traveling salesmen problem
1 Introduction Autonomous navigation is one of the main active research fields in mobile robotic applications. When using multi-robot systems (MRS) for exploration, surveillance,
Electronic supplementary material The online version of this article (https://doi.org/10.1007/s10846-020-01196-y) contains supplementary material, which is available to authorized users. Jo˜ao Paulo Lima Silva de Almeida
[email protected] Renan Taizo Nakashima [email protected] Fl´avio Neves-Jr [email protected] L´ucia Val´eria Ramos de Arruda [email protected] 1
Federal Institute of Paran´a (IFPR), Av. Dr. Tito, s/n, Panorama, Jacarezinho, PR, Brazil
2
Federal University of Technology - Paran´a (UTFPR), Av. Sete de Setembro, 3165, Curitiba, PR, Brazil
object transportation, mapping and similar applications, autonomous navigation requires the development of distributed, cooperative and self-organized solutions [1, 4, 17]. In addition, path planning is an important step to carry out a successfully path to be autonomously navigated by a MRS, mainly in presence of navigation constraints such as partially known and dynamic environment [6, 8]. In several cases, this planning concerns to find a path that requires minimal time and/or distance to achieve a settled goal while maneuvering to avoid collision with obstacles. Global and local solutions are the two main approaches to im
Data Loading...
