Planning robust executions under uncertainty is a fundamental challenge for building autonomous robots. Partially Observable Markov Decision Processes (POMDPs) provide a standard framework for modeling uncertainty in many robot applications. A key algorithmic problem for POMDPs is policy synthesis. While this problem has traditionally been posed w.r.t. optimality objectives, many robot applications are better modeled by POMDPs where the objective is a boolean requirement. In this paper, we study the latter problem in a setting where the requirement is a safe-reachability property, which states that with a probability above a certain threshold, it is possible to eventually reach a goal state while satisfying a safety requirement. The central challenge in our problem is that it requires reasoning over a vast space of probability distributions. What's more, it has been shown that policy synthesis of POMDPs with reachability objectives is undecidable in general. To address these challenges, we introduce the notion of a goal-constrained belief space, which only contains beliefs (probability distributions over states) reachable from the initial belief under desired executions. This constrained space is generally much smaller than the original belief space. Our approach compactly represents this space over a bounded horizon using symbolic constraints, and employs an incremental Satisfiability Modulo Theories (SMT) solver to efficiently search for a valid policy over it. We evaluate our method using a case study involving a partially observable robotics domain with uncertain obstacles. Our results suggest that it is possible to synthesize policies over large belief spaces with a small number of SMT solver calls by focusing on goal-constrained belief space, and our method o ers a stronger guarantee of both safety and reachability than alternative unconstrained constrained POMDP formulations.
Task and Motion Planning (TMP) @cite_19 @cite_3 @cite_12 @cite_32 @cite_18 @cite_20 @cite_26 @cite_41 @cite_10 describes a class of challenging problems that combine low-level motion planning and high-level task reasoning. Most of these TMP approaches focus on deterministic domains, while several of them apply to uncertain domains with uncertainty in perception @cite_3 @cite_12 . The main difference is that, the above works perform planning with a determinized approximation of belief space dynamics @cite_8 assuming the most likely observation will be obtained, while our approach synthesizes a valid policy contingent on all possible events.
@cite_18 @cite_26 @cite_8 @cite_41 @cite_32 @cite_3 @cite_19 @cite_20 @cite_10 @cite_12
2207352740 2055501135 2103052138 2143602574
The execution of long-horizon tasks under uncertainty is a fundamental challenge in robotics. Recent approaches have made headway on these tasks with an integration of task and motion planning. In this paper, we present Interfaced Belief Space Planning (IBSP): a modular approach to task and motion planning in belief space. We use a task-independent interface layer to combine an off-the-shelf classical planner with motion planning and inference. We determinize the problem under the maximum likelihood observation assumption to obtain a deterministic representation where successful plans generate goal-directed observations. We leverage properties of maximum likelihood observation determinizations to obtain a simple representation of (optimistic) belief space dynamics that is well-suited to planning. Our interface is implemented with standard belief state queries, requiring only the ability to sample, compute unnormalized likelihoods, and compute maximum likelihood states. Our contribution is a novel algorithm for task and motion planning in belief space that has minimal dependence on the details of the inference engine used. IBSP can work with a broad class of black box state estimators, with zero changes to the algorithm. We validate our approach in simulated tasks for the PR2 that account for continuous state, different types of initial state distributions, and negative observations. This paper presents a generic approach for tactical decision-making under uncertainty in the context of driving. The complexity of this task mainly stems from the fact that rational decision-making in this context must consider several sources of uncertainty: The temporal evolution of situations cannot be predicted without uncertainty because other road users behave stochastically and their goals and plans cannot be measured. Even more important, road users are only able to perceive a tiny part of the current situation with their sensors because measurements are noisy and most of the environment is occluded. In order to anticipate the consequences of decisions a probabilistic approach, considering both forms of uncertainty, is necessary. The authors address this by formulating the task of driving as a continuous Partially Observable Markov Decision Process (POMDP) that can be automatically optimized for different scenarios. As driving is a continuous-space problem, the belief space is infinite-dimensional. The authors do not use a symbolic representation or discretize the state space a priori because there is no representation of the state space that is optimal for every situation. Instead, they employ a continuous POMDP solver that learns a good representation of the specific situation. In this paper we address the problem of motion planning in the presence of state uncertainty, also known as planning in belief space. The work is motivated by planning domains involving nontrivial dynamics, spatially varying measurement properties, and obstacle constraints. To make the problem tractable, we restrict the motion plan to a nominal trajectory stabilized with a linear estimator and controller. This allows us to predict distributions over future states given a candidate nominal trajectory. Using these distributions to ensure a bounded probability of collision, the algorithm incrementally constructs a graph of trajectories through state space, while efficiently searching over candidate paths through the graph at each iteration. This process results in a search tree in belief space that provably converges to the optimal path. We analyze the algorithm theoretically and also provide simulation results demonstrating its utility for balancing information gathering to reduce uncertainty and finding low cost paths. We present a formal framework that combines high-level representation and causality-based reasoning with low-level geometric reasoning and motion planning. The frame-work features bilateral interaction between task and motion planning, and embeds geometric reasoning in causal reasoning, thanks to several advantages inherited from its underlying components. In particular, our choice of using a causality-based high-level formalism for describing action domains allows us to represent ramifications and state transition constraints, and embed in such formal domain descriptions externally defined functions implemented in some programming language (e.g., C++). Moreover, given such a domain description, the causal reasoner based on this formalism (i.e., the Causal Calculator) allows us to compute optimal solutions (e.g., shortest plans) for elaborate planning prediction problems with temporal constraints. Utilizing these features of high-level representation and reasoning, we can combine causal reasoning, motion planning and geometric planning to find feasible kinematic solutions to task-level problems. In our framework, the causal reasoner guides the motion planner by finding an optimal task-plan; if there is no feasible kinematic solution for that task-plan then the motion planner guides the causal reasoner by modifying the planning problem with new temporal constraints. Furthermore, while computing a task-plan, the causal reasoner takes into account geometric models and kinematic relations by means of external predicates implemented for geometric reasoning (e.g., to check some collisions); in that sense the geometric reasoner guides the causal reasoner to find feasible kinematic solutions. We illustrate an application of this framework to robotic manipulation, with two pantograph robots on a complex assembly task that requires concurrent execution of actions. A short video of this application accompanies the paper.