改良された分離トレードオフによるラベルなしマルチロボット運動計画

要旨: 多角形環境における単位円盤ロボットの、ラベルなしマルチロボット運動計画を研究する。本問題は一般には難しいが、出発位置と目標位置に関する適切な分離仮定のもとでは、多項式時間解が存在する。Banyassady ら（SoCG'22）は、開始—開始および目標—目標距離が少なくとも 4、さらに開始—目標距離が少なくとも 3 であるという条件のもとで、単純多角形において実行可能性を保証しているが、最適性の保証はない。Solovey ら（RSS'15）は、より厳しい条件のもとで、一般の多角形領域に対して近似最適な解を与えている。具体的には、開始/目標位置の対ごとの距離が少なくとも 4 であり、かつ障害物から少なくとも
\sqrt{5}\approx2.236 離れている必要がある。このことから、さらに密に詰め込まれた環境でも多項式時間アルゴリズムが得られるのか、という疑問が生じる。
本論文では、ロボット間分離と障害物間分離の境界に関して異なるトレードオフを達成する一般化アルゴリズムを提示し、具体的には従来技術を大幅に改善する。具体的には、（i）ロボット間分離が 2\tfrac{2}{3} で障害物間分離が 1\tfrac{2}{3}、または（ii）ロボット間分離が約 3.291 で障害物間分離が約 1.354 のときに、総経路長を最小化する多項式時間の定数近似アルゴリズムを得る。さらに、ロボット間分離がわずか 2、障害物間分離が 3 のときに、多項式時間の解を与える別の戦略も導入する。最後に、ロボット間分離の仮定なしでは、解が存在するために障害物間分離が少なくとも 1.5 必要であることを示す。