Abstract— A core capability of robots is to reason about mul-
tiple objects under uncertainty. Partially Observable Markov
Decision Processes (POMDPs) provide a means of reasoning
under uncertainty for sequential decision making, but are
computationally intractable in large domains. In this paper,
we propose Object-Oriented POMDPs (OO-POMDPs), which
represent the state and observation spaces in terms of classes
and objects. The structure afforded by OO-POMDPs support
a factorization of the agent’s belief into independent object
distributions, which enables the size of the belief to scale linearly
versus exponentially in the number of objects. We formulate
a novel Multi-Object Search (MOS) task as an OO-POMDP
for mobile robotics domains in which the agent must find the
locations of multiple objects. Our solution exploits the structure
of OO-POMDPs by featuring human language to selectively
update the belief at task onset. Using this structure, we develop
a new algorithm for efficiently solving OO-POMDPs: Object-
Oriented Partially Observable Monte-Carlo Planning (OO-
POMCP). We show that OO-POMCP with grounded language
commands is sufficient for solving challenging MOS tasks both
in simulation and on a physical mobile robot.
more »
« less
Task-Directed Exploration in Continuous POMDPs for Robotic Manipulation of Articulated Objects
Representing and reasoning about uncertainty is crucial for autonomous
agents acting in partially observable environments with noisy
sensors. Partially observable Markov decision processes (POMDPs) serve
as a general framework for representing problems in which uncertainty
is an important factor. Online sample-based POMDP methods have emerged
as efficient approaches to solving large POMDPs and have been shown to
extend to continuous domains. However, these solutions struggle to
find long-horizon plans in problems with significant
uncertainty. Exploration heuristics can help guide planning, but many
real-world settings contain significant task-irrelevant uncertainty
that might distract from the task objective. In this paper, we propose
STRUG, an online POMDP solver capable of handling domains that require
long-horizon planning with significant task-relevant and
task-irrelevant uncertainty. We demonstrate our solution on several
temporally extended versions of toy POMDP problems as well as robotic
manipulation of articulated objects using a neural perception frontend
to construct a distribution of possible models. Our results show that
STRUG outperforms the current samplebased online POMDP solvers on
several tasks.
more »
« less
- Award ID(s):
- 2214177
- NSF-PAR ID:
- 10444338
- Date Published:
- Journal Name:
- IEEE International Conference on Robotics and Automation
- ISSN:
- 1049-3492
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)This work presents novel techniques for tightly integrated online information fusion and planning in human-autonomy teams operating in partially known environments. Motivated by dynamic target search problems, we present a new map-based sketch interface for online soft-hard data fusion. This interface lets human collaborators efficiently update map information and continuously build their own highly flexible ad hoc dictionaries for making language-based semantic observations, which can be actively exploited by autonomous agents in optimal search and information gathering problems. We formally link these capabilities to POMDP algorithms for optimal planning under uncertainty, and develop a new Dynamically Observable Monte Carlo planning (DOMCP) algorithm as an efficient means for updating online sampling-based planning policies for POMDPs with non-static observation models. DOMCP is validated on a small scale robot localization problem, and then demonstrated with our new user interface on a simulated dynamic target search scenario in a partially known outdoor environment.more » « less
-
This paper presents a hybrid online Partially Observable Markov Decision Process (POMDP) planning system that addresses the problem of autonomous navigation in the presence of multi-modal uncertainty introduced by other agents in the environment. As a particular example, we consider the problem of autonomous navigation in dense crowds of pedestrians and among obstacles. Popular approaches to this problem first generate a path using a complete planner (e.g., Hybrid A*) with ad-hoc assumptions about uncertainty, then use online tree-based POMDP solvers to reason about uncertainty with control over a limited aspect of the problem (i.e. speed along the path). We present a more capable and responsive real-time approach enabling the POMDP planner to control more degrees of freedom (e.g., both speed AND heading) to achieve more flexible and efficient solutions. This modification greatly extends the region of the state space that the POMDP planner must reason over, significantly increasing the importance of finding effective roll-out policies within the limited computational budget that real time control affords. Our key insight is to use multi-query motion planning techniques (e.g., Probabilistic Roadmaps or Fast Marching Method) as priors for rapidly generating efficient roll-out policies for every state that the POMDP planning tree might reach during its limited horizon search. Our proposed approach generates trajectories that are safe and significantly more efficient than the previous approach, even in densely crowded dynamic environments with long planning horizons.more » « less
-
Abstract To be responsive to dynamically changing real-world environments, an intelligent agent needs to perform complex sequential decision-making tasks that are often guided by commonsense knowledge. The previous work on this line of research led to the framework called interleaved commonsense reasoning and probabilistic planning (i corpp ), which used P-log for representing commmonsense knowledge and Markov Decision Processes (MDPs) or Partially Observable MDPs (POMDPs) for planning under uncertainty. A main limitation of i corpp is that its implementation requires non-trivial engineering efforts to bridge the commonsense reasoning and probabilistic planning formalisms. In this paper, we present a unified framework to integrate i corpp ’s reasoning and planning components. In particular, we extend probabilistic action language pBC + to express utility, belief states, and observation as in POMDP models. Inheriting the advantages of action languages, the new action language provides an elaboration tolerant representation of POMDP that reflects commonsense knowledge. The idea led to the design of the system pbcplus2pomdp , which compiles a pBC + action description into a POMDP model that can be directly processed by off-the-shelf POMDP solvers to compute an optimal policy of the pBC + action description. Our experiments show that it retains the advantages of i corpp while avoiding the manual efforts in bridging the commonsense reasoner and the probabilistic planner.more » « less
-
more » « less
Partially observable Markov decision processes (POMDPs) provide a flexible representation for real-world decision and control problems. However, POMDPs are notoriously difficult to solve, especially when the state and observation spaces are continuous or hybrid, which is often the case for physical systems. While recent online sampling-based POMDP algorithms that plan with observation likelihood weighting have shown practical effectiveness, a general theory characterizing the approximation error of the particle filtering techniques that these algorithms use has not previously been proposed. Our main contribution is bounding the error between any POMDP and its corresponding finite sample particle belief MDP (PB-MDP) approximation. This fundamental bridge between PB-MDPs and POMDPs allows us to adapt any sampling-based MDP algorithm to a POMDP by solving the corresponding particle belief MDP, thereby extending the convergence guarantees of the MDP algorithm to the POMDP. Practically, this is implemented by using the particle filter belief transition model as the generative model for the MDP solver. While this requires access to the observation density model from the POMDP, it only increases the transition sampling complexity of the MDP solver by a factor of O(C), where C is the number of particles. Thus, when combined with sparse sampling MDP algorithms, this approach can yield algorithms for POMDPs that have no direct theoretical dependence on the size of the state and observation spaces. In addition to our theoretical contribution, we perform five numerical experiments on benchmark POMDPs to demonstrate that a simple MDP algorithm adapted using PB-MDP approximation, Sparse-PFT, achieves performance competitive with other leading continuous observation POMDP solvers.
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
