Efficiently finding optimal winding-constrained loops in the plane

Paul Vernaza, Venkatraman Narayanan, and Maxim Likhachev
Proceedings of Robotics: Science and Systems, July, 2012.


Download
  • Adobe portable document format (pdf) (7MB)
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.

Abstract
We present a method to efficiently find winding- constrained loops in the plane that are optimal with respect to a minimum-cost objective and in the presence of obstacles. Our approach is similar to a typical graph-based search for an optimal path in the plane, but with an additional state variable that encodes information about path homotopy. Upon finding a loop, the value of this state corresponds to a line integral over the loop that indicates how many times it winds around each obstacle, enabling us to reduce the problem of finding paths satisfying winding constraints to that of searching for paths to suitable states in this augmented state space. We give an intuitive interpretation of the method based on fluid mechanics and show how this yields a way to perform the necessary calculations efficiently. Results are given in which we use our method to find optimal routes for autonomous surveillance and intruder containment.

Notes

Text Reference
Paul Vernaza, Venkatraman Narayanan, and Maxim Likhachev, "Efficiently finding optimal winding-constrained loops in the plane," Proceedings of Robotics: Science and Systems, July, 2012.

BibTeX Reference
@inproceedings{Vernaza_2012_7345,
   author = "Paul Vernaza and Venkatraman Narayanan and Maxim Likhachev",
   title = "Efficiently finding optimal winding-constrained loops in the plane",
   booktitle = "Proceedings of Robotics: Science and Systems",
   month = "July",
   year = "2012",
}