06月12日(Tue) 15:30〜20:00 E会場(-山口県教育会館／第四研修室(72))
| 演題番号 | 1E3-OS-4-10 |
|---|---|
| 題目 | Near Optimal Cooperative Path Planning in Hard Setups through Satisfiability Solving |
| 著者 | Surynek Pavel(神戸大学大学院海事科学研究科,Charles University, Prague) |
| 時間 | 06月12日(Tue) 18:50〜19:10 |
| 概要 | 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 state-of-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 sub-solutions. 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 sub-optimal planner is available. |
| 論文 | PDFファイル |