Towards Optimal Cooperative Path Planning in Hard Setups through Satisfiability Solving
Towards Optimal Cooperative Path Planning in Hard Setups through Satisfiability Solving
复制标题
DOI：
10.1007/978-3-642-32695-0_50
复制
发表时间：
2012-09
期刊：
影响因子：
--
通讯作者：
Pavel Surynek
中科院分区：
文献类型：
--
作者：
Pavel Surynek
提出了一种新的协同路径规划方法。SAT解算器不是用来求解整个实例，而是用来优化次优解的完成时间。这种方法试图利用最先进的SAT解算器的能力，快速给出相对较小的实例的解决方案。首先利用已有的方法求出该实例的次优解。然后将其提交给优化过程，优化过程将其分解成小的子序列，SAT求解器为这些子序列找到最优解。然后，作为最优子解的串联得到新的较短的解。该过程反复进行，直到达到固定点。这是为人口稠密的环境产生接近最优解决方案的第一种方法；它也可以应用于与域无关的规划，假设有次优规划器可用。
A novel approach to cooperative path-planning is presented. A SAT solver is used not to solve the whole instance but for optimizing the makespan of a sub-optimal solution. This approach is trying to exploit the ability of stateof- the-art SAT solvers to give a solution to relatively small instance quickly. A sub-optimal solution to the instance is obtained by some existent method first. It is then submitted to the optimization process which decomposes it into small subsequences for which optimal solutions are found by a SAT solver. The new shorter solution is subsequently obtained as concatenation of optimal subsolutions. The process is iterated until a fixed point is reached. This is the first method to produce near optimal solutions for densely populated environments; it can be also applied to domain-independent planning supposed that suboptimal planner is available.