Optimization of Focused Wave Front Algorithm in Unknown Dynamic Environment for Multi-Robot Navigation

Optimization of Focused Wave Front Algorithm in Unknown Dynamic Environment for Multi-Robot Navigation

Priyanka Meel, Ritu Tiwari, Anupam Shukla
Copyright: © 2013 |Pages: 29
DOI: 10.4018/ijimr.2013100101
(Individual Articles)
No Current Special Offers


Robotics is a field which includes multiple disciplines such as environment mapping, localization, path planning, path execution, area exploration etc. Path planning is the elementary requirement for all the above mentioned diversified fields. This paper presents a new method for motion planning of mobile robots which carry forward the best features of Focused Wave Front and other wave front based path planners, at the same time optimizes the algorithm in terms of path length, energy consumption and memory requirements. This research introduces a method of choosing every next step in grid based environment and also proposes a backtracking procedure to minimize turns by means of identifying landmark points in the path. Further, the authors have enhanced the functionality of Focused Wave Front algorithm by applying it in uncertain dynamic environment. The proposed method is a combination of global and local path planning as well as online and offline navigation process. A new method based on bidirectional wave propagation along the walls of obstacle and wall following behavior is being proposed for avoiding uncertain static obstacles. Considering the criticalness of moving obstacles a colored safety zone is assumed to have around them and the robot is equipped with color sensitivity. Based on the particular color (red, green, yellow) that has sensed the robot will make intelligent decisions to avoid them. The simulation result reflects how the proposed method has efficiently and safely navigates a robot towards its destination by avoiding all known and unknown obstacles. Finally the algorithms are extended for multi-robot environment.
Article Preview


Path planning of mobile robot is to navigate from source to target without colliding with any of the obstacles in the environment. It mainly incorporates two basic functionalities: goal seeking and obstacle avoidance. In a given environment there are many paths to reach the target but as the navigation process is a constrained optimization problem only one of them is best. So, the objective is to find out the best possible path in the given situation.

Environment plays a vital role in motion planning. According to environment conditions the problem can be classified into two categories: Static environment and Dynamic environment. Static environment is constant throughout but dynamic environment keep on changing as the position of obstacles may change or new dynamic obstacles, vehicles may appear in the map. Based on available information about the environment there are two navigation approaches: Global path planning and Local path planning. In global path planning complete information about the environment is available so path planning is one-time and offline process. But in local path planning path is planned based on the available information from current sensor data, so it is a real time on-line process. Meadow maps, voronoi diagrams, graphs, regular grids, quad trees etc. (Nooraliei, 2009) are several ways of representing the environment. An appropriate way of modeling the environment is required to make the path planning algorithm more efficient and reliable. In our research we have chosen grid based map which is much safer, precise and accurate to be used in static or dynamic environment (Kala, Shukla & Tiwari, 2009).

Mobile robot navigation in dynamic environment with uncertain static and moving obstacles is a real challenge for path planning. Different methods like Potential Field (Khatib & Narendra,1986), Virtual Force Field(VFF) (Borenstein & Koren, 1989) Configuration Space Approach, Dynamic Programming (DP) (Willms, 2006) etc. proposed various solutions for path planning in dynamic environment. It still represents a challenge for the robotics community as the robot has limited resources and has to struggle uncertainty caused by changing and unknown environment. When the obstacle is unknown but it is static, collision avoidance is accomplished by identifying its relative position with respect to environment and robot. On the other hand, if the obstacle is moving apart from its dimensional configurations its direction of motion and speed are also to be identified .So to deal with moving obstacles additional information need to be supplied at real time either to the robot or in the moving obstacle like sound or color (Rooker & Birk, 2007).

Multi-robot systems are the recent area of interest for researchers as the simultaneous use of multiple devices makes the system more fault tolerant and less time consuming. Task assignment, navigation and co-ordination among multiple operating sites are the three main issues in multi-agent systems. Co-ordination can be done in any one of the two ways- Centralized or Distributed. Assignment problem can be considered as ”WHO GOES WHERE”? When there are multiple robots and multiple targets the task should be assigned in such a way that each robot must get only one target and the total cost of assignment can also be minimized (Djekoune, Achour & Toumi, 2009).

Complete Article List

Search this Journal:
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing