Robotics: Science and Systems VI
A Fast Traversal Heuristic and Optimal Algorithm for Effective Environmental Coverage
L. Xu and T. StentzAbstract:
Tasks such as street mapping and security surveillance
seek a route that traverses a given space to perform a
function. These task functions may involve mapping the space
for accurate modeling, sensing the space for unusual activity,
or processing the space for object detection. With a prior map,
an optimal path can be computed using a graph to represent
the environment and generating the solution using known graph
algorithms. However, the prior map may be inaccurate due to
factors such as occlusion, outdatedness, dynamic objects, and
resolution limitations. In this work, we address the NP-hard
problem of optimal environmental coverage with incomplete
prior map information.
To utilize related algorithms in graph theory, we represent the
environment as a graph. Using this representation, we present a
graph coverage approach for optimal plan generation based on
the Undirected Chinese Postman and Rural Postman problems.
This approach produces a tractable solution through the use of
low complexity algorithms in a branch-and-bound framework.
Additionally, as the robot receives sensor updates during traversal
of the environment, we update the graph to reflect those changes.
The updated graph can be highly disconnected so computing an
optimal solution can be NP-hard. To combat this, we introduce
a heuristic for coverage path generation that helps maximize the
connectivity of the updated graph. We evaluate our approach on
a set of comparison tests in simulation.
Bibtex:
@INPROCEEDINGS{ Xu-RSS-10, AUTHOR = {L. Xu AND T. Stentz}, TITLE = {A Fast Traversal Heuristic and Optimal Algorithm for Effective Environmental Coverage}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2010}, ADDRESS = {Zaragoza, Spain}, MONTH = {June}, DOI = {10.15607/RSS.2010.VI.021} }