Search papers, labs, and topics across Lattice.
This paper introduces Graph Sparse Sampling (GSS), an innovative online planning algorithm designed to address the computational challenges of planning in continuous domains by sharing sampled futures across candidate decisions. GSS leverages heuristics to focus computation and proves finite-sample performance guarantees, showing polynomial dependence on the planning horizon, which mitigates the exponential growth of sampling budgets typical in tree-based methods. Experimental results demonstrate that GSS significantly outperforms traditional tree-based planners in continuous-control simulations, particularly in long-horizon scenarios, highlighting its potential as a viable alternative for online control tasks.
GSS reveals that by sharing sampled futures, we can dramatically reduce the computational burden of planning in continuous spaces, breaking the exponential curse of horizon dependence.
Planning under uncertainty in continuous domains is essential for autonomous systems, yet computationally demanding. Tree-based search methods such as Monte Carlo Tree Search (MCTS) remain popular, but their branching structure can require sampling budgets that grow exponentially with lookahead depth in the worst case. From a tree perspective, continuous state or action spaces become especially challenging, since the planner must decide where to search in an infinite branching hierarchy. We propose Graph Sparse Sampling (GSS), an online planning algorithm that shares sampled futures across many candidate decisions, rather than sampling separate successors for each candidate action. This branch-free graph exposes large GPU-friendly batches, while using heuristics to focus computation. We prove finite-sample performance guarantees for GSS covering full-rank or low-rank generative simulators via smoothed backups, and discrete or sampled continuous action spaces. Under suitable overlap, regularity, and action-coverage conditions, these bounds have polynomial dependence on the planning horizon, formalizing when shared futures can avoid the exponential horizon dependence of tree-shaped sparse sampling. We demonstrate continuous-control simulations where GSS substantially outperforms tree-based planners on long horizons or achieves near-optimal performance, supporting no-branching graph planning as a complementary design principle for online control.
