Incremental sampling-based algorithm for minimum-violation motion planning
Incremental sampling-based algorithm for minimum-violation motion planning
复制标题
基于增量采样的最小违规运动规划算法
DOI：
10.1109/cdc.2013.6760374
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
D. Rus
中科院分区：
文献类型：
--
作者：
L. I. R. Castro;P. Chaudhari;Jana Tumova;S. Karaman;Emilio Frazzoli;D. Rus
研究了具有微分约束的动态系统在满足一组安全规则的同时满足给定的可达性目标的控制策略综合问题。特别关注只有在违反安全规则的子集时才变得可行的目标。该算法计算一个控制律，在保证达到预期目标的同时将不安全程度降至最低。这一问题的起因是一辆自动驾驶汽车在城市环境中导航，同时遵守道路规则，如“始终在正确的车道上行驶”和“不要频繁改变车道”。基于采样的运动规划算法背后的思想，如概率道路图(PRM)和快速探索随机树(RRT)，被用来增量地将动力学的有限具体化构造为持续Kriske结构。与此相结合，使用了一个捕获安全规则的加权有限自动机，以便找到最优轨迹，使违反安全规则的行为最小化。我们证明了所提出的算法保证了渐近最优性，即几乎必然收敛于最优解。我们给出了模拟实验的结果和在一个自治的城市移动点播系统上的实现。
This paper studies the problem of control strategy synthesis for dynamical systems with differential constraints to fulfill a given reachability goal while satisfying a set of safety rules. Particular attention is devoted to goals that become feasible only if a subset of the safety rules are violated. The proposed algorithm computes a control law, that minimizes the level of unsafety while the desired goal is guaranteed to be reached. This problem is motivated by an autonomous car navigating an urban environment while following rules of the road such as “always travel in right lane” and “do not change lanes frequently”. Ideas behind sampling based motion-planning algorithms, such as Probabilistic Road Maps (PRMs) and Rapidly-exploring Random Trees (RRTs), are employed to incrementally construct a finite concretization of the dynamics as a durational Kripke structure. In conjunction with this, a weighted finite automaton that captures the safety rules is used in order to find an optimal trajectory that minimizes the violation of safety rules. We prove that the proposed algorithm guarantees asymptotic optimality, i.e., almost-sure convergence to optimal solutions. We present results of simulation experiments and an implementation on an autonomous urban mobility-on-demand system.