Least-Violating Planning in Road Networks from Temporal Logic Specifications
Least-Violating Planning in Road Networks from Temporal Logic Specifications
复制标题
根据时态逻辑规范进行道路网络中最少违规规划
DOI：
10.1109/iccps.2016.7479106
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
D. Rus
中科院分区：
文献类型：
--
作者：
Jana Tumova;S. Karaman;C. Belta;D. Rus
在本文中，我们考虑了在道路网络中运行的车辆的自动计划合成问题，该问题被建模为加权转换系统。车辆被分配了一组需求，每个需求都涉及一个语法上安全的 LTL 公式形式的任务规范、完成该任务的最后期限以及需求优先级。随着车辆的运行，需求逐渐出现，因此需要定期重新规划。我们特别关注所有任务无法在预期期限内完成的情况，并提出了几种不同的方法来衡量需求违反程度，同时考虑到需求优先级。我们基于线性规划问题的转换，开发了一种针对最少违规规划和重新规划问题的通用解决方案。此外，针对特定的需求子类，我们提供了基于图搜索算法的更高效的解决方案。该方法的优点通过受按需移动场景启发的说明性模拟得到了证明。
In this paper, we consider the problem of automated plan synthesis for a vehicle operating in a road network, which is modeled as a weighted transition system. The vehicle is assigned a set of demands, each of which involves a task specification in the form of a syntactically co-safe LTL formula, a deadline for achieving this task, and a demand priority. The demands arrive gradually, upon the run of the vehicle, and hence periodical replanning is needed. We particularly focus on cases, where all tasks cannot be accomplished within the desired deadlines and propose several different ways to measure the degree of demand violation that take into account the demand priorities. We develop a general solution to the problem of least-violating planning and replanning based on a translation to linear programming problem. Furthermore, for a particular subclass of demands, we provide a more efficient solution based on graph search algorithms. The benefits of the approach are demonstrated through illustrative simulations inspired by mobility-on-demand scenarios.