In contrast to classic geometric motion planning, informative path planning (IPP) seeks a path for a robot to sense the world and gain information. In adaptive IPP, the robot chooses the next sensing location conditioned on all information acquired so far, and the robot’s goal is to minimize the travel cost required for identifying a true hypothesis. Adaptive IPP is NP-hard, because the robot must trade-off information gain and travel cost optimally. In this paper we present Recursive Adaptive Identification (RAId), a new polynomial-time approximation algorithm for adaptive IPP. We prove a polylogarithmic approximation bound when the robot travels in a metric space. Furthermore, our experiments suggest that RAId is practical and provides good approximate solutions for two distinct robot planning tasks. Although RAId is designed primarily for noiseless observations, a simple extension allows it to handle some tasks with noisy observations.
CalinescuGZelikovskyA (2005) The polymatroid Steiner problems. Journal of Combinatorial Optimization9(3): 281–294.
2.
ChakaravarthyVTPanditVRoySAwasthiPMohaniaM (2007) Decision trees for entity identification: approximation algorithms and hardness results. In: 26th ACM symposium on principles of database systems, Beijing, China, 11–14 June, pp. 53–62. New York: ACM.
3.
ChekuriCPalM (2005) A recursive greedy algorithm for walks in directed graphs. In: IEEE 46th annual symposium on foundations of computer science, Pittsurgh, USA, 23–25 October, pp. 245–253. Washington DC: IEEE.
4.
ChristofidesN (1976) Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report388, Graduate School of Industrial Administration, Carnegie Mellon University.
5.
DeanBCGoemansMXVondrdkJ (2004) Approximating the stochastic knapsack problem: The benefit of adaptivity. In: IEEE 45th annual symposium on foundations of computer science, Rome, Italy, 17–19 October, pp. 208–217. Washington DC: IEEE.
6.
FederHJSLeonardJJSmithCM (1999) Adaptive mobile robot navigation and mapping. The International Journal of Robotics Research18(7): 650–668.
7.
FoxDBurgardWThrunS (1998) Active Markov localization for mobile robots. Robotics and Autonomous Systems25(3): 195–207.
8.
GolovinDKrauseA (2011) Adaptive submodularity: Theory and applications in active learning and stochastic optimization. Journal of Artificial Intelligence Research42(1): 427–486.
9.
GolovinDKrauseARayD (2010) Near-optimal bayesian active learning with noisy observations. In: 24th annual conference on Neural Information Processing Systems (NIPS), Vancouver, Canada, 6–11 December, pp. 766–774. Palo Alto: AAAI Press.
10.
GuptaANagarajanVRaviR (2010) Approximation algorithms for optimal decision trees and adaptive TSP problems. In: 37th international colloquium conference on automata, languages and programming (Lecture Notes in Computer Science, vol. 6198): 690–701. Heidelberg: Springer.
11.
HollingerGSukhatmeG (2013) Sampling-based motion planning for robotic information gathering. In: 2013 robotics: science and systems conference, Berlin, Germany, 24–28 June. Cambridge, MA: MIT Press.
12.
HollingerGSinghSDjugashJKehagiasA (2009) Efficient multi-robot search for a moving target. The International Journal of Robotics Research28(2): 201–219.
13.
HollingerGMitraUSukhatmeG (2011) Active classification: Theory and application to underwater inspection. In: 15th international symposium on robotics research, Flagstaff, USA, 28 August–1 September. Heidelberg: Springer.
14.
HollingerGEnglotBHoverFSMitraUSukhatmeGS (2013) Active planning for underwater inspection and the benefit of adaptivity. The International Journal of Robotics Research32(1): 3–18.
15.
JavdaniSKlingensmithMBagnellJAPollardNSrinivasaSS (2013) Efficient touch based localization through submodularity. In: 2013 IEEE international conference on robotics and automation, Karlsruhe, Germany, 6–10 May, pp. 1828–1835. New York: IEEE.
16.
JavdaniSChenYKarbasiAKrauseABagnellJASrinivasaS (2014) Near optimal Bayesian active learning for decision making. In: 17th international conference on artificial intelligence & statistics, Reykjavik, Iceland, 22–25 April. Brookline: Microtome.
17.
KaelblingLPLittmanMLCassandraAR (1998) Planning and acting in partially observable stochastic domains. Artificial Intelligence101(1–2): 99–134.
18.
KrauseAGuestrinC (2009) Optimal value of information in graphical models. Journal of Artificial Intelligence Research35(1): 557–591.
19.
KurniawatiHHsuDLeeWS (2008) SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In: Robotics: science and systems IV, Zurich, Switzerland, 25–27 June, pp. 65–72. Cambridge, MA: MIT Press.
20.
PineauJGordonGThrunS (2003) Point-based value iteration: An anytime algorithm for POMDPs. In: 18th international joint conference on artificial intelligence, Acapulco, Mexico, 9–15 August, pp. 1025–1030. San Francisco: Morgan Kaufmann.
21.
PlattRJrKaelblingLPLozanoT-PerezTedrakeR (2011) Simultaneous localization and grasping as a belief space control problem. In: 15th international symposium on Robotics Research, Flagstaff, USA, 28 August–1 September. Heidelberg: Springer.
22.
SinghAKrauseAGuestrinCKaiserWJ (2009) Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research34(2): 707–755a.
23.
SinghAKrauseAKaiserWJ (2009)b Nonmyopic adaptive informative path planning for multiple robots. In: 21st international joint conference on artificial intelligence, pp. 1043–1050. San Francisco: Morgan Kaufmann.
24.
SmithTSimmonsR (2005) Point-based POMDP algorithms: Improved analysis and implementation. In: 21st conference on uncertainty in artificial intelligence, Los Angeles, USA, 10–12 July, pp. 542–549. Arlington: AUAI Press.
25.
ZhengAXRishIBeygelzimerA (2005) Efficient test selection in active diagnosis via entropy approximation. In: 21st conference on uncertainty in artificial intelligence, Los Angeles, USA, 10–12 July, pp. 675–682. Arlington: AUAI Press.
