1
|
Hoerger M, Kurniawati H, Elfes A. Multilevel Monte Carlo for solving POMDPs on-line. Int J Rob Res 2022. [DOI: 10.1177/02783649221093658] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
Abstract
Planning under partial observability is essential for autonomous robots. A principled way to address such planning problems is the Partially Observable Markov Decision Process (POMDP). Although solving POMDPs is computationally intractable, substantial advancements have been achieved in developing approximate POMDP solvers in the past two decades. However, computing robust solutions for systems with complex dynamics remains challenging. Most on-line solvers rely on a large number of forward simulations and standard Monte Carlo methods to compute the expected outcomes of actions the robot can perform. For systems with complex dynamics, for example, those with non-linear dynamics that admit no closed-form solution, even a single forward simulation can be prohibitively expensive. Of course, this issue exacerbates for problems with long planning horizons. This paper aims to alleviate the above difficulty. To this end, we propose a new on-line POMDP solver, called Multilevel POMDP Planner (MLPP), that combines the commonly known Monte-Carlo-Tree-Search with the concept of Multilevel Monte Carlo to speed up our capability in generating approximately optimal solutions for POMDPs with complex dynamics. Experiments on four different problems involving torque control, navigation and grasping indicate that MLPP substantially outperforms state-of-the-art POMDP solvers.
Collapse
Affiliation(s)
- Marcus Hoerger
- School of Mathematics and Physics, The University of Queensland, Australia
| | - Hanna Kurniawati
- School of Computing, The Australian National University, Canberra, ACT, Australia
| | - Alberto Elfes
- Robotics and Autonomous Systems Group, Data61, CSIRO, Pullenvale, QLD, Australia
| |
Collapse
|
2
|
Canal G, Cashmore M, Krivić S, Alenyà G, Magazzeni D, Torras C. Probabilistic Planning for Robotics with ROSPlan. TOWARDS AUTONOMOUS ROBOTIC SYSTEMS 2019. [DOI: 10.1007/978-3-030-23807-0_20] [Citation(s) in RCA: 11] [Impact Index Per Article: 2.2] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/18/2023]
|
3
|
Abstract
The partially observable Markov decision process (POMDP) provides a principled general framework for robot planning under uncertainty. Leveraging the idea of Monte Carlo sampling, recent POMDP planning algorithms have scaled up to various challenging robotic tasks, including, real-time online planning for autonomous vehicles. To further improve online planning performance, this paper presents IS-DESPOT, which introduces importance sampling to DESPOT, a state-of-the-art sampling-based POMDP algorithm for planning under uncertainty. Importance sampling improves DESPOT’s performance when there are critical, but rare events, which are difficult to sample. We prove that IS-DESPOT retains the theoretical guarantee of DESPOT. We demonstrate empirically that importance sampling significantly improves the performance of online POMDP planning for suitable tasks. We also present a general method for learning the importance sampling distribution.
Collapse
Affiliation(s)
- Yuanfu Luo
- Department of Computer Science, National University of Singapore, Singapore
| | | | - David Hsu
- Department of Computer Science, National University of Singapore, Singapore
| | - Wee Sun Lee
- Department of Computer Science, National University of Singapore, Singapore
| |
Collapse
|
4
|
Pineda LA, Rodríguez A, Fuentes G, Hernández N, Reyes M, Rascón C, Cruz R, Vélez I, Ortega H. Opportunistic inference and emotion in service robots. JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2018. [DOI: 10.3233/jifs-169512] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/15/2022]
Affiliation(s)
- Luis A. Pineda
- Departamento de Ciencias de la Computación, Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas (IIMAS), Universidad Nacional Autónoma de México (UNAM)
| | - Arturo Rodríguez
- Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México (UNAM)
| | - Gibrán Fuentes
- Departamento de Ciencias de la Computación, Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas (IIMAS), Universidad Nacional Autónoma de México (UNAM)
| | - Noé Hernández
- Departamento de Ciencias de la Computación, Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas (IIMAS), Universidad Nacional Autónoma de México (UNAM)
| | - Mauricio Reyes
- Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México (UNAM)
- Centro de Investigaciones en Diseño Industrial (CIDI), Facultad de Arquitectura, Universidad Nacional Autónoma de México (UNAM)
| | - Caleb Rascón
- Departamento de Ciencias de la Computación, Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas (IIMAS), Universidad Nacional Autónoma de México (UNAM)
- Consejo Nacional de Ciencia y Tecnología (CONACyT), México
| | - Ricardo Cruz
- Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México (UNAM)
| | - Ivette Vélez
- Posgrado en Ciencia e Ingeniería de la Computación, Universidad Nacional Autónoma de México (UNAM)
| | - Hernando Ortega
- Departamento de Probabilidad y Estadística, Instituto de Investigaciones en Matemáticas Aplicadas y en Sistemas (IIMAS), Universidad Nacional Autónoma de México (UNAM)
| |
Collapse
|
5
|
Homberg BS, Katzschmann RK, Dogar MR, Rus D. Robust proprioceptive grasping with a soft robot hand. Auton Robots 2018. [DOI: 10.1007/s10514-018-9754-1] [Citation(s) in RCA: 72] [Impact Index Per Article: 12.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/29/2022]
|
6
|
Kurniawati H, Yadav V. An Online POMDP Solver for Uncertainty Planning in Dynamic Environment. SPRINGER TRACTS IN ADVANCED ROBOTICS 2016. [DOI: 10.1007/978-3-319-28872-7_35] [Citation(s) in RCA: 43] [Impact Index Per Article: 5.4] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 12/12/2022]
|
7
|
Koval MC, Pollard NS, Srinivasa SS. Pre- and post-contact policy decomposition for planar contact manipulation under uncertainty. Int J Rob Res 2015. [DOI: 10.1177/0278364915594474] [Citation(s) in RCA: 28] [Impact Index Per Article: 3.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
Abstract
We consider the problem of using real-time feedback from contact sensors to create closed-loop pushing actions. To do so, we formulate the problem as a partially observable Markov decision process (POMDP) with a transition model based on a physics simulator and a reward function that drives the robot towards a successful grasp. We demonstrate that it is intractable to solve the full POMDP with traditional techniques and introduce a novel decomposition of the policy into pre- and post-contact stages to reduce the computational complexity. Our method uses an offline point-based solver on a variable-resolution discretization of the state space to solve for a post-contact policy as a pre-computation step. Then, at runtime, we use an A* search to compute a pre-contact trajectory. We prove that the value of the resulting policy is within a bound of the value of the optimal policy and give intuition about when it performs well. Additionally, we show the policy produced by our algorithm achieves a successful grasp more quickly and with higher probability than a baseline QMDP policy on two different objects in simulation. Finally, we validate our simulation results on a real robot using commercially available tactile sensors.
Collapse
Affiliation(s)
- Michael C. Koval
- The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA
| | - Nancy S. Pollard
- The Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, USA
| | | |
Collapse
|
8
|
Chen D, Liu Z, von Wichert G. Uncertainty-Aware Arm-Base Coordinated Grasping Strategies for Mobile Manipulation. J INTELL ROBOT SYST 2015. [DOI: 10.1007/s10846-015-0234-y] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 10/23/2022]
|
9
|
Abstract
The partially observable Markov decision process (POMDP) provides a principled mathematical model for integrating perception and planning, a major challenge in robotics. While there are efficient algorithms for moderately large discrete POMDPs, continuous models are often more natural for robotic tasks, and currently there are no practical algorithms that handle continuous POMDPs at an interesting scale. This paper presents an algorithm for continuous-state, continuous-observation POMDPs. We provide experimental results demonstrating its potential in robot planning and learning under uncertainty and a theoretical analysis of its performance. A direct benefit of the algorithm is to simplify model construction.
Collapse
|
10
|
Abstract
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.
Collapse
|
11
|
Capitan J, Spaan MT, Merino L, Ollero A. Decentralized multi-robot cooperation with auctioned POMDPs. Int J Rob Res 2013. [DOI: 10.1177/0278364913483345] [Citation(s) in RCA: 70] [Impact Index Per Article: 6.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/17/2022]
Abstract
Planning under uncertainty faces a scalability problem when considering multi-robot teams, as the information space scales exponentially with the number of robots. To address this issue, this paper proposes to decentralize multi-robot partially observable Markov decision processes (POMDPs) while maintaining cooperation between robots by using POMDP policy auctions. Auctions provide a flexible way of coordinating individual policies modeled by POMDPs and have low communication requirements. In addition, communication models in the multi-agent POMDP literature severely mismatch with real inter-robot communication. We address this issue by exploiting a decentralized data fusion method in order to efficiently maintain a joint belief state among the robots. The paper presents two different applications: environmental monitoring with unmanned aerial vehicles (UAVs); and cooperative tracking, in which several robots have to jointly track a moving target of interest. The first one is used as a proof of concept and illustrates the proposed ideas through different simulations. The second one adds real multi-robot experiments, showcasing the flexibility and robust coordination that our techniques can provide.
Collapse
|
12
|
Bai H, Hsu D, Lee WS, Ngo VA. Monte Carlo Value Iteration for Continuous-State POMDPs. SPRINGER TRACTS IN ADVANCED ROBOTICS 2010. [DOI: 10.1007/978-3-642-17452-0_11] [Citation(s) in RCA: 35] [Impact Index Per Article: 2.5] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 01/21/2023]
|