COVERAGE PATH-PLANNING FOR SINGLE AND MULTI-ROBOT SYSTEMS
Through my undergraduate project work, I came across the potentials of evolutionary optimization algorithm in solving various NP hard problems such as coverage path planning of mobile robots. This inspired me to carry out further study and research in this area.
Summary: Coverage path planning can be described as a task where given a vehicle and an area filled with obstacles, a path needs to be computed for the vehicle such that by following the path the vehicle adequately transverse all the area. It is a fundamental problem with numerous practical applications. Cleaning interiors, sowing seed or plowing a field, lawn mowing, and searching for objects using metal detector are just a few examples.
State of the art: Previous works on coverage pathplanning can be classified as either randomized or coordinated. Coordinate approaches (S. X. Yang et al, 2003, E. Acar et al, 2001) need high quality sensors such as ultrasonic or laser in order to obtain map of the cleaning scenario. They also require very high on-board computational power than the simpler robots. Where as randomized approaches such as reactive planning (Brom, C., 2005) is highly inefficient due to multiple overlapping of the cleaned path which leads to waste of time and energy.
Project Description: In this work, a novel approach to coverage path planning problem is introduced. Here, an attempt has been made to develop a genetic algorithm based coverage strategy that directs a team of robots with limited sensor capability to cover an unknown terrain in a systematic manner solely based on footprint data left by randomized path planning robot previously operated on that area. Simple robots will follow their assigned path simultaneously. They will collectively cover most of the reachable part of the workspace with minimum path overlapping and at the same time manages to avoid all obstacles. The proposed pathplanning algorithm incorporate both coordinated and randomized aspects in order to (hopefully) exploit the best of both worlds. At one hand it assigns robot a specific path in order to maximize the efficiency. On the other hand it is applicable to simple mobile robot with very few sensors. Samples of the result are provided in Figure below. The nodes are numbered in the order in which the mobile robot are planned to visit. Here the cells are covered by Boustrophedon motion (Fig. 6). When the robot enters an "unclean" cell, the boustrophedic motion is planned and then it moved to the next node as planned. When the robot enters a "cleaned" cell, it simply plans a path through that cell to the next node in the path list.
Fig 1. Paths left by randomized path-planning Robots
Fig 2. Graph constructed from those paths
Fig. 3. Construction of Cells
Fig. 4. Cells decomposed to monotone polygons
Fig. 5. Coverage Path-planning for the single robot
Fig. 6. Boustrophedon motion with in a cell
Fig 7(a) Coverage path-planning for two robots. Here shown for the first robot
Fig 7(b) Coverage path-planning for the second robot
This work has been published at: Journal papers: 1. Md. Ahsan Habib, M.S. Alam and N.H. Siddique, "Optimizing Coverage Performance of Multiple Random Path-planning Robots," Paladyn. Journal of Behavioral Robotics, 2011(accepted).
Conference Papers: 1. Md. Ahsan Habib, Rahatir Rashid, M.S. Alam, and M.A. Hossain, A Genetic Approach to Optimize the Floor Cleaning Performance of a Random Path-planning mobile robot, “The International Conference on Software, Knowledge and Information Management and Applications (SKIMA 2009)”, Fes, Morocco during October 21-23, 2009. 2. Md. Ahsan Habib, M.S. Alam, F. Aldbrez and N.H. Siddique, A Genetic Approach to Optimize the Coverage Performance of Multiple Random Path-planning Robots, “The 12th International Conference on Climbing and Walking Robots and the Support Technologies for Mobile Machines (CLAWAR 2009)”, Istanbul, Turkey, 09 - 11 September 2009, Paper ID 174, pp. 1091-1099.