保証付き・予測可能な多項式時間AGV経路計画
Guaranteed, Predictable, Polynomial AGV Time-Pathing
任意のグラフ上で任意の位置から任意の要求を満たすAGVの時刻表を、満たしやすい仮定の下で多項式時間で保証付き生成するアルゴリズムとデータ構造を提案し、地理的予約アルゴリズムをO(nm)からO(n)に改善した。
著者: James Forster
分類: cs.CE, cs.DS, cs.IT, cs.RO, cs.SY, eess.SY, math.IT
原文アブストラクト
In this paper we present a framework of key algorithms and data-structures for efficiently generating timetables for any number of AGVs from any given positioning on any given graph to accomplish any given demands as long as a few easily satisfiable assumptions are met. Our proposed algorithms provide guaranteed solutions in predictable polynomial running-times, which is fundamental to any real-time application. We also develop an improved geographic reservation algorithm that provides a substantial run-time improvement of the previously best-known algorithm from $O(nm)$ to $O(n)$.