Planning with movable obstacles in continuous environments with uncertain dynamics

In this paper we present a decision theoretic planner for the problem of Navigation Among Movable Obstacles (NAMO) operating under conditions faced by real robotic systems. While planners for the NAMO domain exist, they typically assume a deterministic environment or rely on discretization of the configuration and action spaces, preventing their use in practice. In contrast, we propose a planner that operates in real-world conditions such as uncertainty about the parameters of workspace objects and continuous configuration and action (control) spaces. To achieve robust NAMO planning despite these conditions, we introduce a novel integration of Monte Carlo simulation with an abstract MDP construction. We present theoretical and empirical arguments for time complexity linear in the number of obstacles as well as a detailed implementation and examples from a dynamic simulation environment.

Authors

• Martin Levihn
• Jonathan Scholz
• Mike Stilman

Keywords

• Robots
• Planning
• Monte Carlo methods
• Uncertainty
• Abstracts
• Aerospace electronics
• Friction
• Movable Obstacles
• Deterministic
• Monte Carlo Simulation
• Robotic System
• Configuration Space
• Markov Decision Process
• Objective Parameters
• Continuous Action Space
• Theoretical Analysis
• State Space
• Free Space
• Friction Coefficient
• Continuous State
• Transition Model
• Reward Function
• Transition Dynamics
• Stochastic Simulations
• Abstract Representations
• Unknown Environment
• Value Iteration
• Monte Carlo Tree Search
• Continuous State Space
• General Inference
• Free Region
• Discrete State Space
• Reward Model
• Dynamic Uncertainties
• Physics Engine
• Friction Force
• Statistical Inference