A PSO-Inspired Multi-Robot Map Exploration Algorithm Using Frontier-Based Strategy

A PSO-Inspired Multi-Robot Map Exploration Algorithm Using Frontier-Based Strategy

Yi Zhou (School of Software, Shanghai Jiao Tong University, Shanghai, China), Kai Xiao (School of Software, Shanghai Jiao Tong University, Shanghai, China), Yiheng Wang (School of Software, Shanghai Jiao Tong University, Shanghai, China), Alei Liang (School of Software, Shanghai Jiao Tong University, Shanghai, China) and Aboul Ella Hassanien (Information Technology Department, Cairo University, Giza, Egypt)
Copyright: © 2013 |Pages: 13
DOI: 10.4018/ijsda.2013040101
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Map exploration is a fundamental problem in mobile robots. This paper presents a distributed algorithm that coordinates a team of autonomous mobile robots to explore an unknown environment. The proposed strategy is based on frontiers which are the regions on the boundary between open and unexplored space. With this strategy, robots are guided to move constantly to the nearest frontier to reduce the size of unknown region. Based on the Particle Swarm Optimization (PSO) model incorporated in the algorithm, robots are navigated towards remote frontier after exploring the local area. The exploration completes when there is no frontier cell in the environment. The experiments implemented on both simulated and real robot scenarios show that the proposed algorithm is capable of completing the exploration task. Compared to the conventional method of randomly selecting frontier, the proposed algorithm proves its efficiency by the decreased 60% exploration time at least. Additional experimental results show the decreased coverage time when the number of robots increases, which further suggests the validity, efficiency and scalability.
Article Preview

1. Introduction

Exploring unknown environment is a fundamental problem in mobile robotics. Yamauchi (1998) defines “exploration” as “Given what you know about the world, where should you move to gain as much new information as possible”. Robots must know more information about their surroundings before performing complex tasks in a previously unknown environment. There are many applications of this scenario, such as: planetary exploration (Apostolopouslos, 2001), search (Qian, 2011), rescue (Murphy, 2004; Thrun, 2003; Baxter, 2002; Kantor, 2003), cleaning (Endres, 1998; Jäger, 2002), map building, hazardous material handling, military actions, etc. Compared to single robot system, multi-robot system receives better performance in reliability, robustness, efficiency and flexibility (Cao, 1997; Dudek, 1996). First, because of covering the environment in parallel, multi-robot system has the potential to complete exploration more quickly. Furthermore, the redundancy of robots provides robustness, since the breakdown of any robot does not severely degrade the performance of the system.

There are many factors affecting the overall performance of the multi-robot robot exploration process, such as robots moving to the same unexplored area, repeated coverage (a region visited more than once), the blockage and collision situation and the growth of communication when the number of robots increases.

Reynolds (1987) presents the model of Boids which simulates the flocking behavior of birds. Based on this idea, Kennedy and Eberhart (1995) proposed a novel population-based stochastic technique — Particle Swarm Optimization (PSO). PSO is widely used optimization algorithm in Swarm Intelligence (SI) research. Although it is an original application in the area of SI, swarm robotics still faces several challenging issues when using PSO algorithm. One of these issues is the difference between PSO and multi-robot task allocation optimization (Pugh, 2007). For example, the state of particles is called ‘reaching an agreement’ when all particles are on the same point in cognitive space. In multi-robot systems, when the robots and obstacles collide, they share the same position. As a result, it is necessary to design an avoidance algorithm. Furthermore, particles in PSO have a fitness value which is computed by the fitness function. In most situations, multi-robot task allocation optimization cannot provide the fitness function directly. Finally, in the real environment, robots are navigated to move, explore and sense in a more complex and unstable situation, compared to the abstract solution space in PSO algorithm. Therefore, it is required to find alternative solutions for applying the PSO model in this scenario.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 6: 4 Issues (2017)
Volume 5: 4 Issues (2016)
Volume 4: 4 Issues (2015)
Volume 3: 4 Issues (2014)
Volume 2: 4 Issues (2013)
Volume 1: 4 Issues (2012)
View Complete Journal Contents Listing