# Search-Based Path Planning in Interactive Environments among Movable Obstacles

arXiv: https://arxiv.org/abs/2410.18333 · HTML: https://mlsanity.com/paper/2410.18333/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 23 references that are in the map.
- First posted on arXiv 24 Oct 2024.

## Builds on (most cited first, 7 of 7)

- [Interactive Gibson Benchmark (iGibson 0.5): A Benchmark for Interactive Navigation in Cluttered Environments](https://mlsanity.com/paper/1910.14442/) (2019)
- [Manipulation Planning Among Movable Obstacles Using Physics-Based Adaptive Motion Primitives](https://mlsanity.com/paper/2102.04324/) (2021)
- [Multi-Objective Path-Based D* Lite](https://mlsanity.com/paper/2108.00710/) (2021)
- [Enhanced Multi-Objective A* Using Balanced Binary Search Trees](https://mlsanity.com/paper/2202.08992/) (2022)
- [A Conflict-Based Search Framework for Multi-Objective Multi-Agent Path Finding](https://mlsanity.com/paper/2101.03805/) (2021)
- [Interactive-FAR:Interactive, Fast and Adaptable Routing for Navigation Among Movable Obstacles in Complex Unknown Environments](https://mlsanity.com/paper/2404.07447/) (2024)
- [Enhanced Methods for the Weight Constrained Shortest Path Problem](https://mlsanity.com/paper/2207.14744/) (2022)

## Abstract (arXiv)

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.