Planning long journeys from random moves in unfamiliar environments
Learning to Plan from Random Exploration
Machine LearningRobotics
Summary
Planning a route in a new place usually needs practice toward a goal, but this research shows it can be done just by exploring randomly first. The authors explain how taking many random steps reveals the shape and connections of the space at different distances. They build a model that learns to understand these time-based relationships without needing information about actions or rewards. This model helps an agent plan actions step by step by predicting how each move would bring it closer to a target, even when starting from random wandering.
What this means in practice
- •For robot developers: Enable robots to plan routes and manipulation tasks after random movements without goal-specific training or rewards.
- •For video game designers: Design AI characters that explore and navigate complex environments naturally from random exploration, improving realism without extensive scripting.
Authors
Deqian Kong, Guangyan Sun, Sheng Cheng, Sirui Xie, Bo Pang, Jianwen Xie, Tony Geng, Caiwen Ding, Ying Nian Wu
Abstract
Random exploration reveals how an environment can be traversed before a goal is specified. Can this experience support long-range planning without policy-improvement training? Our random-walk analysis explains what temporal relations contain: short horizons reveal geodesic geometry in the diffusion limit, while longer horizons reveal connectivity between regions before mixing removes these distinctions. We learn these relations with a conditional energy-based model that estimates temporal log-density ratios through horizon-conditioned embeddings. The model is trained on observation pairs by noise-contrastive estimation, without action or reward labels. The planner queries these learned relations at different horizons as it moves toward the goal. At test time, a separate local dynamics model predicts candidate action outcomes, and the temporal model evaluates their progress toward the goal by selecting or aggregating estimated improvements across horizons. The agent executes one action and replans with both models fixed. Experiments demonstrate long-range maze planning from random exploration using states and images. Learned score fields, embedding probes, and planned routes exhibit properties of a multiscale cognitive map. We further demonstrate egocentric navigation from random exploration and manipulation planning from suboptimal data.