Search-Based Path Planning in Interactive Environments among Movable Obstacles
This paper investigates Path planning Among Movable Obstacles (PAMO), which seeks a minimum cost collision-free path among static obstacles from start to goal while allowing the robot to push away movable obstacles (i.e., objects) along its path when needed. To develop planners that are complete and optimal for PAMO, the planner has to search a giant state space involving both the location of the robot as well as the locations of the objects, which grows exponentially with respect to the number of objects. This paper leverages a simple yet under-explored idea that, only a small fraction of this giant state space needs to be searched during planning as guided by a heuristic, and most of the objects far away from the robot are intact, which thus leads to runtime efficient algorithms. Based on this idea, this paper introduces two PAMO formulations, i.e., bi-objective and resource constrained problems in an occupancy grid, and develops PAMO*, a planning method with completeness and solution optimality guarantees, to solve the two problems. We then further extend PAMO* to hybrid-state PAMO* to plan in continuous spaces with high-fidelity interaction between the robot and the objects. Our results show that, PAMO* can often find optimal solutions within a second in cluttered maps with up to 400 objects.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
LLM A*: Human in the Loop Large Language Models Enabled A* Search for Robotics
This research focuses on how Large Language Models (LLMs) can help with (path) planning for mobile embodied agents such as robots, in a human-in-the-loop and interactive manner. A novel framework named LLM A*, aims to le…
Adaptive Interactive Navigation of Quadruped Robots using Large Language Models
Robotic navigation in complex environments remains a critical research challenge. Traditional navigation methods focus on optimal trajectory generation within free space, struggling in environments lacking viable paths t…
Motion PlanningTask PlanningPath Planning Followed by Kinodynamic Smoothing for Multirotor Aerial Vehicles (MAVs)
We explore path planning followed by kinodynamic smoothing while ensuring the vehicle dynamics feasibility for MAVs. We have chosen a geometrically based motion planning technique \textquotedblleft RRT*\textquotedblright…
Motion PlanningSpeeding Up Path Planning via Reinforcement Learning in MCTS for Automated Parking
In this paper, we address a method that integrates reinforcement learning into the Monte Carlo tree search to boost online path planning under fully observable environments for automated parking tasks. Sampling-based pla…
reinforcement-learningReinforcement LearningPaiP: An Operational Aware Interactive Planner for Unknown Cabinet Environments
Box/cabinet scenarios with stacked objects pose significant challenges for robotic motion due to visual occlusions and constrained free space. Traditional collision-free trajectory planning methods often fail when no col…
Trajectory Planning