Sampling-based tree search with discrete abstractions for motion planning with dynamics and temporal logic
Sampling-based tree search with discrete abstractions for motion planning with dynamics and temporal logic
复制标题
基于采样的树搜索，具有离散抽象，用于动态和时序逻辑的运动规划
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
E. Plaku
中科院分区：
文献类型：
--
作者：
J. McMahon;E. Plaku
本文提出了一种高效的方法，用于规划无碰撞、动态可行且低成本的运动轨迹，这些轨迹满足以一种时态逻辑（即语法上协同安全的线性时态逻辑，LTL）公式形式给出的任务规范。该规划器面向在复杂环境中运行且具有非线性动力学的高维移动机器人。规划器结合了基于物理的引擎，用于精确模拟刚体动力学。为了获得计算效率并生成低成本的解决方案，规划器首先通过将表示LTL公式的自动机与工作空间分解相结合来施加离散抽象。然后，规划器利用离散抽象将在状态空间中扩展的基于采样的运动树划分为等价类。每个等价类都捕捉了在实现时态逻辑规范方面所取得的进展。在抽象上定义的启发式方法用于估计从这些等价类扩展运动树并达到接受自动机状态的可行性。成本根据所取得的进展进行调整，使规划器在发现新的扩展搜索方法的同时能够灵活地快速取得进展。与相关工作的比较表明，在计算速度上有统计学意义的显著提高，并且解决方案成本降低。
This paper presents an efficient approach for planning collision-free, dynamically-feasible, and low-cost motion trajectories that satisfy task specifications given as formulas in a temporal logic, namely Syntactically Co-Safe Linear Temporal Logic (LTL). The planner is geared toward high-dimensional mobile robots with nonlinear dynamics operating in complex environments. The planner incorporates physics-based engines for accurate simulations of rigid-body dynamics. To obtain computational efficiency and generate low-cost solutions, the planner first imposes a discrete abstraction by combining an automaton representing the LTL formula with a workspace decomposition. The planner then uses the discrete abstraction to induce a partition of a sampling-based motion tree being expanded in the state space into equivalence classes. Each equivalence class captures the progress made toward achieving the temporal logic specifications. Heuristics defined over the abstraction are used to estimate the feasibility of expanding the motion tree from these equivalence classes and reaching an accepting automaton state. Costs are adjusted based on progress made, giving the planner the flexibility to make rapid progress while discovering new ways to expand the search. Comparisons to related work show statistically significant computational speedups and reduced solution costs.