在连续域的不确定性下进行规划对于自治系统, 至关重要，但计算要求较高。基于树的搜索方法（例如蒙特卡罗树搜索(MCTS)）仍然很受欢迎,，但它们的分支结构可能需要在最坏情况下随着前瞻深度呈指数增长的采样预算。从树的角度来看，, 连续状态或动作空间变得特别具有挑战性,，因为规划器必须决定在无限分支层次结构中搜索何处。我们提出图稀疏采样 (GSS), 一种在线规划算法，该算法在许多候选决策, 之间共享采样的未来，而不是为每个候选动作采样单独的后继者。这个无分支图公开了大型 GPU 友好批次,，同时使用启发式方法来集中计算。我们通过平滑备份, 和离散或采样连续动作空间，证明了覆盖全秩或低秩生成模拟器的 GSS 的有限样本性能保证。在适当的重叠,规则性,和行动覆盖条件,下，这些界限对规划范围,具有多项式依赖性，当共享未来形式化时可以避免树形稀疏采样的指数范围依赖性。我们演示了连续控制模拟，其中 GSS 在长期范围内大大优于基于树的规划器，或实现接近最优的性能, 支持无分支图规划作为在线控制的补充设计原则。
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.
科目:人工智能(cs.AI)
Subjects: Artificial Intelligence (cs.AI)