Sage Journals: Discover world-class research

Abstract

We propose three sampling-based motion planning algorithms for generating informative mobile robot trajectories. The goal is to find a trajectory that maximizes an information quality metric (e.g. variance reduction, information gain, or mutual information) and also falls within a pre-specified budget constraint (e.g. fuel, energy, or time). Prior algorithms have employed combinatorial optimization techniques to solve these problems, but existing techniques are typically restricted to discrete domains and often scale poorly in the size of the problem. Our proposed rapidly exploring information gathering (RIG) algorithms combine ideas from sampling-based motion planning with branch and bound techniques to achieve efficient information gathering in continuous space with motion constraints. We provide analysis of the asymptotic optimality of our algorithms, and we present several conservative pruning strategies for modular, submodular, and time-varying information objectives. We demonstrate that our proposed techniques find optimal solutions more quickly than existing combinatorial solvers, and we provide a proof-of-concept field implementation on an autonomous surface vehicle performing a wireless signal strength monitoring task in a lake.

Keywords

Motion and path planning field robotics robotic information gathering

Get full access to this article

View all access options for this article.

References

Bajcsy

(1988) Active perception. Proceedings of the IEEE, Special Issue on Computer Vision 76(8): 966–1005.

Binney

Sukhatme

(2012) Branch and bound for informative path planning. In: Proceedings of the IEEE International conference on robotics and automation, St Paul, MN, USA, 14–18 May 2012, pp. 2147–2154.

Bourgault

Furukawa

Durrant-Whyte

(2003) Coordinated decentralized search for a lost target in a Bayesian world. In: Proceedings of the IEEE/RSJ International conference intelligent robots and systems, Las Vegas, NV, USA, 27 October–1 November 2003, pp. 48–53.

Bourgault

Makarenko

Williams

. (2002) Information based adaptive robotic exploration. In: IEEE/RSJ International conference on intelligent robots and systems, Vol. 1, Lausanne, Switzerland, 30 September–4 October 2002, pp. 540–545.

Bry

Roy

(2011) Rapidly-exploring random belief trees for motion planning under uncertainty. In: Proceedings of the IEEE International conference on robotics and automation, Shanghai, 9–13 May 2011, pp. 723–730.

Cameron

Durrant-Whyte

(1990) A Bayesian approach to optimal sensor placement. International Journal of Robotics Research 9(5): 70–88.

Chen

Kwok

(2011) Active vision in robotic systems: A survey of recent developments. International Journal of Robotics Research 30(11): 1343–1377.

Fiorelli

Leonardi

Bhatta

. (2006) Multi-AUV control and adaptive sampling in Monterey Bay. IEEE Journal of Oceanic Engineering 31(4): 935–948.

Hollinger

Englot

Hover

. (2013) Active planning for underwater inspection and the benefit of adaptivity. International Journal of Robotics Research 32(1): 3–18.

10.

Hollinger

Singh

Djugash

. (2009) Efficient multi-robot search for a moving target. International Journal of Robotics Research 28(2): 201–219.

11.

Hollinger

Sukhatme

(2013) Sampling-based motion planning for robotic information gathering. In: Proceedings of the Robotics: Science and systems conference, Berlin, Germany.

12.

Hsiao

Kaelbling

Lozano-Pérez

(2010) Task-driven tactile exploration. In: Proceedings of the Robotics: Science and systems conference, Zaragoza, Spain.

13.

Karaman

Frazzoli

(2011) Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research 30(7): 846–894.

14.

Karaman

Walter

Perez

. (2011) Anytime motion planning using the RRT*. In: IEEE International conference on robotics and automation, Shanghai, 9–13 May 2011, pp. 1478–1483.

15.

Kavraki

Svestka

Latombe

. (1996) Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12(4): 566–580.

16.

Krause

Guestrin

(2011) Submodularity and its applications in optimized information gathering. ACM Transactions on Intelligent Systems and Technology 2(4).

17.

Lan

Schwager

(2013) Planning periodic persistent monitoring trajectories for sensing robots in Gaussian random fields. In: Proceedings of the IEEE International conference on robotics and automation, Karlsruhe, Germany, 6–10 May 2013, pp. 2407–2412.

18.

Latombe

(1991) Robot Motion Planning. Boston, MA: Kluwer Academic Publishers.

19.

LaValle

(2006) Planning Algorithms. Cambridge: Cambridge University Press.

20.

LaValle

Kuffner

(2001) Randomized kinodynamic planning. International Journal of Robotics Research 20(5): 378–400.

21.

Levine

(2010) Information-rich path planning under general constraints using rapidly-exploring random trees. Master’s Thesis, Massachusetts Institute of Technology, Cambridge, MA, USA.

22.

Low

Dolan

Khosla

(2009) Information-theoretic approach to efficient adaptive path planning for mobile robotic environmental sensing. In: Proceedings of the International conference on automated planning and scheduling, Thessaloniki, Greece, pp. 233–240.

23.

Myers

Williams

(2010) A POMDP for multi-view target classification with an autonomous underwater vehicle. In: Proceedings of the IEEE OCEANS conference, Seattle, WA, USA.

24.

Rasmussen

Williams

CKI

(2006) Gaussian Processes for Machine Learning. Cambridge, MA: MIT Press.

25.

Reif

(1979) Complexity of the mover’s problem and generalizations. In: Proceedings of the IEEE Symposium on the Foundations of Computer Science, San Juan, Puerto Rico, pp. 421–427.

26.

Ryan

Hedrick

(2010) Particle filter based information-theoretic active sensing. Robotics and Autonomous Systems 58(5): 574–584.

27.

Singh

Krause

Guestrin

. (2009) Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research 34: 707–755.

28.

Smith

Schwager

Smith

. (2011) Persistent ocean monitoring with underwater gliders: Adapting sampling resolution. Journal of Field Robotics 28(5): 714–741.

29.

Şucan

Moll

Kavraki

(2012) The open motion planning library. IEEE Robotics and Automation Magazine 19(4): 72–82.

30.

Thompson

Chien

Chao

. (2010) Spatiotemporal path planning in strong, dynamic, uncertain currents. In: Proceedings of the IEEE International conference on robotics and automation, Anchorage, AK, USA, 3–8 May 2010, pp. 4778–4783.

31.

Thrun

(1999) Monte carlo POMDPs. In: Proceedings of the neural information processing systems conference, Vancouver, Canada, pp. 1064–1070.

32.

Van den Berg

Patil

Alterovitz

(2012) Motion planning under uncertainty using iterative local optimization in belief space. International Journal of Robotics Research 31(11): 1263–1278.

33.

Vasudevan

Ramos

Nettleton

. (2009) Gaussian process modeling of large scale terrain. Journal of Field Robotics 26(10): 812–840.

34.

Wald

(1945) Sequential tests of statistical hypotheses. Annals of Mathematical Statistics 16(2): 117–186.

35.

Weber

(2010) Simple methods for evaluating and comparing binary experiments. Theory and Decision 69(2): 257–288.

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB

Sampling-based robotic information gathering algorithms

Abstract

Keywords

Get full access to this article

References

Supplementary Material