Broadly-Exploring, Local-Policy Trees for Long-Horizon Task Planning

2020/10/13 by Brian Ichter, Pierre Sermanet, Ichter, Brian +3 · 3 citations
Computer Science · #AI-based Problem Solving and Planning #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Robotic Path Planning Algorithms #Robotics (cs.RO)

paper · pdf · doi:10.48550/arxiv.2010.06491

openalex publication_date 2020/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Long-horizon planning in realistic environments requires the ability to reason over sequential tasks in high-dimensional state spaces with complex dynamics. Classical motion planning algorithms, such as rapidly-exploring random trees, are capable of efficiently exploring large state spaces and computing long-horizon, sequential plans. However, these algorithms are generally challenged with complex, stochastic, and high-dimensional state spaces as well as in the presence of narrow passages, which naturally emerge in tasks that interact with the environment. Machine learning offers a promising solution for its ability to learn general policies that can handle complex interactions and high-dimensional observations. However, these policies are generally limited in horizon length. Our approach, Broadly-Exploring, Local-policy Trees (BELT), merges these two approaches to leverage the strengths of both through a task-conditioned, model-based tree search. BELT uses an RRT-inspired tree search to efficiently explore the state space. Locally, the exploration is guided by a task-conditioned, learned policy capable of performing general short-horizon tasks. This task space can be quite general and abstract; its only requirements are to be sampleable and to well-cover the space of useful tasks. This search is aided by a task-conditioned model that temporally extends dynamics propagation to allow long-horizon search and sequential reasoning over tasks. BELT is demonstrated experimentally to be able to plan long-horizon, sequential trajectories with a goal conditioned policy and generate plans that are robust.

Citations

• Multi-Level Discovery of Deep Options
• Data-Efficient Hierarchical Reinforcement Learning
• Learning Latent Dynamics for Planning from Pixels
• Model-Based Reinforcement Learning for Atari
• Why Does Hierarchy (Sometimes) Work So Well in Reinforcement Learning?

Cited by

• Deep Reactive Policy: Learning Reactive Manipulator Motion Planning for Dynamic Environments
• Train-Once Plan-Anywhere Kinodynamic Motion Planning via Diffusion Trees
• Hierarchical Planning with Latent World Models

Related

• Forecaster: Towards Temporally Abstract Tree-Search Planning from Pixels
• Flexible and Efficient Long-Range Planning Through Curious Exploration
• Seeing the Forest Despite the Trees: Large Scale Spatial-Temporal Decision Making
• Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees
• Combining Neural Networks and Tree Search for Task and Motion Planning in Challenging Environments