Path Planning for Robotic Demining: Robust Sensor-Based Coverage of Unstructured Environments and Probabilistic Methods

Ercan Acar, Howie Choset, Yangang Zhang and Mark Schervish
Journal Article, Carnegie Mellon University, The International Journal of Robotics Research, Vol. 22, No. 8-Jul, pp. 441 - 466, July, 2003

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


Demining and unexploded ordnance (UXO) clearance are extremely tedious and dangerous tasks. The use of robots bypasses the hazards and potentially increases the efficiency of both tasks. A first crucial step towards robotic mine/UXO clearance is to locate all the targets. This requires a path planner that generates a path to pass a detector over all points of a mine/UXO field, i.e., a planner that is complete.The current state of the art in path planning for mine/UXO clearance is to move a robot randomly or use simple heuristics. These methods do not possess completeness guarantees which are vital for locating all of the mines/UXOs. Using such random approaches is akin to intentionally using imperfect detectors. In this paper, we first overview our prior complete coverage algorithm and compare it with randomized approaches. In addition to the provable guarantees, we demonstrate that complete coverage achieves coverage in shorter time than random coverage. We also show that the use of complete approaches enables the creation of a filter to reject bad sensor readings, which is necessary for successful deployment of robots. We propose a new approach to handle sensor uncertainty that uses geometrical and topological features rather than sensor uncertainty models. We have verified our results by performing experiments in unstructured indoor environments. Finally, for scenarios where some a priori information about a minefield is available, we expedite the demining process by introducing a probabilistic method so that a demining robot does not have to perform exhaustive coverage.

author = {Ercan Acar and Howie Choset and Yangang Zhang and Mark Schervish},
title = {Path Planning for Robotic Demining: Robust Sensor-Based Coverage of Unstructured Environments and Probabilistic Methods},
journal = {The International Journal of Robotics Research},
year = {2003},
month = {July},
volume = {22},
number = {8-Jul},
pages = {441 - 466},
} 2017-09-13T10:44:34-04:00