Skip to content

Model Predictive Trees: Sample-Efficient Receding Horizon Planning with Reusable Tree Search

Authors: John Lathrop, Benjamin Rivière, Jedidiah Alindogan, Soon-Jo Chung

Published: 2024 (Conference Paper)

Source: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)

Algorithm: MPT

arXiv: 2411.15651

DOI: 10.1109/IROS58592.2024.10802673

Summary

Proposes reusing the entire optimal subtree (not just the best trajectory) across receding horizon planning steps, enabling simultaneous refinement toward better solutions and away from worse ones.

Abstract

We present Model Predictive Trees (MPT), a receding horizon tree search algorithm that improves its performance by reusing information efficiently. Whereas existing solvers reuse only the highest-quality trajectory from the previous iteration as a "hotstart", our method reuses the entire optimal subtree, enabling the search to be simultaneously guided away from the low-quality areas and towards the high-quality areas. We characterize the restrictions on tree reuse by analyzing the induced tracking error under time-varying dynamics, revealing a tradeoff between the search depth and the timescale of the changing dynamics. In numerical studies, our algorithm outperforms state-of-the-art sampling-based cross-entropy methods with hotstarting. We demonstrate our planner on an autonomous vehicle testbed performing a nonprehensile manipulation task: pushing a target object through an obstacle field. Code associated with this work will be made available at https://github.com/jplathrop/mpt.

Primary

Paper arxiv.org

Standard

arXiv Abstract 2411.15651 arXiv PDF 2411.15651 arXiv HTML 2411.15651 DOI 10.1109/IROS58592.2024.10802673

Alternate

ieeexplore.ieee.org ieeexplore.ieee.org researchgate.net researchgate.net

Tags

  • Model Predictive Control

  • Tree search

  • Monte Carlo Tree Search

  • Receding horizon planning

  • Motion planning

  • Robotics

  • Sample efficiency