We describe an integrated strategy for planning, perception, state estimation and action in complex mobile manipulation domains based on planning in the belief space of probability distributions over states using hierarchical goal regression (pre-image back-chaining). We develop a vocabulary of logical expressions that describe sets of belief states, which are goals and subgoals in the planning process. We show that a relatively small set of symbolic operators can give rise to task-oriented perception in support of the manipulation goals. An implementation of this method is demonstrated in simulation and on a real PR2 robot, showing robust, flexible solution of mobile manipulation problems with multiple objects and substantial uncertainty.
AlterovitzRSimeonTGoldbergK (2007) The stochastic motion roadmap: A sampling framework for planning with Markov motion uncertainty. In: Proceedings of the Robotics Science and Systems Conference.
2.
BarryJLKaelblingLPLozano-PérezT (2011) DetH*: Approximate hierarchical solution of large Markov decision processes. In: Proceedings of the International Joint Conference on Artificial Intelligence.
BertoliPCimattiARoveriMTraversoP (2001) Planning in nondeterministic domains under partial observability via symbolic model checking. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 473–478.
BlumALangfordJ (1999) Probabilistic planning in the graphplan framework. In: European Conference on Planning, pp. 319–332.
7.
BonetBGeffnerH (2011) Planning under partial observability by classical replanning: Theory and experiments. In: Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
8.
BrafmanRILatombeJMosesYShohamY (1997) Applications of a logic of knowledge to motion planning under uncertainty. Journal of the ACM44: 668.
9.
BryceDKambhampatiSSmithDE (2006) Planning graph heuristics for belief space search. Journal of Artificial Intelligence Research26: 35–99.
10.
CambonSAlamiRGravotF (2009) A hybrid approach to intricate motion, manipulation and task planning. International Journal of Robotics Research28.
11.
CassandraARKaelblingLPKurienJA (1996) Acting under uncertainty: Discrete bayesian models for mobile robot navigation. In: Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems.
12.
DogarMSrinivasaS (2012) A planning framework for non-prehensile manipulation under clutter and uncertainty. Autonomous Robots33: 217–236.
13.
DonaldB (1988) A geometric approach to error detection and recovery for robot motion planning with uncertainty. Artificial Intelligence37: 223–271.
14.
DornhegeCGisslerMTeschnerMNebelB (2009) Integrating symbolic and geometric planning for mobile manipulation. In: IEEE International Workshop on Safety, Security and Rescue Robotics.
15.
du ToitNEBurdickJW (2010) Robotic motion planning in dynamic, cluttered, uncertain environments. In: IEEE Conference on Robotics and Automation.
16.
ElfesA (1989) Using occupancy grids for mobile robot perception and navigation. Computer22: 46–57.
17.
ErdmannM (1994) Using backprojection for fine motion planning with uncertainty. The International Journal of Robotics Research5: 240–271.
18.
ErezTSmartW (2010) A scalable method for solving high-dimensional continuous POMDPs using local approximation. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence.
19.
FletcherPTJoshiSLuCPizerS (2003) Gaussian distributions on Lie groups and their application to statistical shape analysis. In: Proceedings of Information Processing in Medical Imaging. pp. 450–462.
20.
FritzCMcIlraithSA (2009a) Computing robust plans in continuous domains. In: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS).
21.
FritzCMcIlraithSA (2009b) Generating optimal plans in highly-dynamic domains. In: Proceedings of the Conference on Uncertainty in Artificial Intelligence.
22.
GellySSilverD (2008) Achieving master level play in 9 x 9 computer GO. In: Proceedings of the Association for the Advancement of Artificial Intelligence, pp. 1537–1540.
23.
GhallabMNauDSTraversoP (2004) Automated Planning: Theory and Practice. Amsterdam: Elsevier.
24.
HauserK (2010) Randomized belief-space replanning in partially-observable continuous spaces. In: Workshop on Algorithmic Foundations of Robotics.
25.
HsiaoKKaelblingLPLozano-PérezT (2007) Grasping POMDPs. In: Proceedings of the IEEE International Conference on Robotics and Automation.
26.
JulierSJUhlmannJK (2004) Unscented filtering and nonlinear estimation. IEEE Review92: 401–422.
27.
KaelblingLPLozano-PérezT (2011) Hierarchical task and motion planning in the now. In: IEEE Conference on Robotics and Automation.
28.
KaelblingLPLozano-PérezT (2012a) Integrated Robot Task and Motion Planning in the Now. Technical Report 2012-018, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology.
29.
KaelblingLPLozano-PérezT (2012b) Integrated Task and Motion Planning in Belief Space. Technical Report 2012-019, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology.
30.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research30: 846–894.
31.
KeyderEGeffnerH (2008) The HMDP planner for planning with probabilities. In: Sixth International Planning Competition at ICAPS08.
32.
KuffnerJJJrLaValleSM (2000) RRT-Connect: An efficient approach to single-query path planning. In: Proceedings of the IEEE International Conference on Robotics and Automation (ICRA).
33.
KurniawatiHDuYHsuDLeeWS (2011) Motion planning under uncertainty for robotic tasks with long time horizons. The International Journal of Robotics Research30: 308–323.
34.
KurniawatiHHsuDLeeWS (2008) SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. In: Robotics Science and Systems.
LaValleSM (2006) Planning Algorithms. Cambridge: Cambridge University Press.
37.
LevihnMScholzJStilmanM (2012) Hierarchical decision theoretic planning for navigation among movable obstacles. In: Proceedings of the Workshp on the Algorithmic Foundations of Robotics (WAFR).
38.
Lozano-PérezT (1983) Spatial planning: a configuration space approach. IEEE Transactions on Computers32: 108–120.
39.
Lozano-PérezTMasonMTaylorRH (1984) Automatic synthesis of fine-motion strategies for robots. The International Journal of Robotics Research3: 3–24.
40.
Lozano-PérezTWesleyMA (1979) An algorithm for planning collison-free paths among polyhedral obstacles. Communications of the ACM22: 560–570.
41.
MarthiBRussellSWolfeJ (2010) Combined task and motion planning for mobile manipulation. In: Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS).
42.
MausamKolobovA (2012) Planning with Markov Decision Processes (Synthesis Lectures on Artificial Intelligence and Machine Learning). Morgan & Claypool Publishers.
43.
MayneDMichalskaH (1990) Receding horizon control of nonlinear systems. IEEE Transactions on Automatic Control35: 814–824.
44.
McCarthyJHayesPJ (1969) Some philosophical problems from the standpoint of artificial intelligence. In: MeltzerBMichieD (eds.), Machine Intelligence 4. Edinburgh: Edinburgh University Press, pp. 463–502.
45.
MooreRC (1985) A formal theory of knowledge and action. In: HobbsJRMooreRC (eds.) Formal Theories of the Commonsense World. Norwood, NJ: Ablex Publishing Company.
46.
MorgensternL (1987) Knowledge preconditions for actions and plans. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 867–874.
47.
NilssonNJ (1985) Triangle Tables: A Proposal for a Robot Programming Language. Technical Report 347, Artificial Intelligence Center, SRI International, Menlo Park, CA.
48.
OngSCWPngSWHsuDLeeWS (2010) Planning under uncertainty for robotic tasks with mixed observability. The International Journal of Robotics Research29: 1053–1068.
49.
PangercicDTenorthMJainDBeetzM (2010) Combining perception and knowledge for everyday manipulation. In: IEEE Conference on Intelligent Robots and Systems.
50.
PetrickRPABacchusF (2004) Extending the knowledge-based approach to planning with incomplete information and sensing. In: International Conference on Automated Planning and Scheduling.
51.
PlakuEHagerG (2010) Sampling-based motion planning with symbolic, geometric, and differential constraints. In: Proceedings of the IEEE Conference on Robotics and Automation.
52.
PlattRTedrakeRKaelblingLPLozano-PérezT (2010) Belief space planning assuming maximum likelihood observations. In: Robotics: Science and Systems.
53.
PrenticeSRoyN (2007) The belief roadmap: Efficient planning in linear POMDPs by factoring the covariance. In: International Symposium on Robotics Research.
54.
RomanoJMHsiaoKNiemeyerGChittaSKuchenbecherKJ (2011) Human-inspired robotic grasp control with tactile sensing. IEEE Transactions on Robotics27: 1067–1079.
55.
RusuRBSucanIAGerkeyBPChittaSBeetzMKavrakiLE (2009) Real-time perception-guided motion planning for a personal robot. In: IEEE Conference on Intelligent Robots and Systems, St. Louis, MO.
56.
SannerSKerstingK (2010) Symbolic dynamic programming for first-order POMDPs. In: Proceedings of the Association for the Advancement of Artificial Intelligence.
57.
SimmonsRKoenigS (1995) Probabilistic robot navigation in partially observable environments. In: Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1080–1087.
58.
SmallwoodRDSondikEJ (1973) The optimal control of partially observable Markov processes over a finite horizon. Operations Research21: 1071–1088.
59.
SouzaASantanaABrittoRGoncalvesLMedeirosA (2008) Representation of odometry errors on occupancy grids. In: International Conference on Informatics in Control, Automation and Robotics.
60.
SrinivasaSFergusonDHelfrichC. (2009) HERB: A home exploring robotic butler. Journal of Autonomous Robots28: 5–20.
61.
StilmanMKuffnerJJ (2006) Planning among movable obstacles with artificial constraints. In: Proceedings of the Workshop on Algorithmic Foundations of Robotics (WAFR).
62.
ThielscherM (2005) Flux: A logic programming method for reasoning agents. Theory and Practice of Logic Programming5: 533–565.
63.
ThrunSBurgardWFoxD (2005) Probabilistic Robotics. Cambridge, MA: MIT Press.
64.
TuanLCBaralCSonTC (2006) A state-based regression formulation for domains with sensing actions and incomplete information. Logical Methods in Computer Science2(4): 1–34.
65.
van den BergJAbbeelPGoldbergKY (2011) LQG-MP: Optimized path planning for robots with motion uncertainty and imperfect state information. The International Journal of Robotics Research30: 895–913.
66.
WangCKhardonR (2010) Relational partially observable MDPs. In: Proceedings of the Association for the Advancement of Artificial Intelligence.
67.
WongLLKaelblingLPLozano-PérezT (2013) Manipulation-based active search for occluded objects. In: IEEE Conference on Robotics and Automation.
68.
WongLLSKaelblingLPLozano-PerezT (2012) Collision-free state estimation. In: IEEE Conference on Robotics and Automation.
69.
WurmKMHornungABennewitzMStachnissCBurgardW (2010) OctoMap: A probabilistic, flexible, and compact 3D map representation for robotic systems. In: ICRA Workshop on Best Practice in 3D Perception and Modeling for Mobile Manipulation.
70.
YoonSWFernAGivanR (2007) FF-Replan: A baseline for probabilistic planning. In: International Conference on Automated Planning and Scheduling.
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.
