最近、arXivに掲載された論文「On the Hardness of Optimal Motion on Trees」において、著者のTzvika Geftは、ツリー構造上のマルチエージェント経路探索（MAPF）の複雑性を解決するシンプルなフレームワークを提案しました。この研究は、距離、メイクスパン、フロータイムの3つの標準的な目的関数と、ラベル付きおよび色付きの2つのバリアントを対象としています。
MAPF問題では、複数のエージェントがグラフの頂点を占有し、衝突を避けながら目標頂点に移動し、所与の目的を最適化します。ラベル付きバリアントでは各エージェントは個別で目標が指定されますが、色付きバリアントでは同じ色のエージェントは交換可能です。多くのMAPFの変種が困難であることが知られている一方で、ツリー上の基本的なケースは長らく未解決のままでした。
本論文の主な成果は、ツリー上でラベル付きMAPFと2色MAPFのすべての目的関数に対してNP困難性を証明したことです。これにより、古典的なペブル移動問題（Pebble Motion Problem）の複雑性が解決されました。この問題では、一度に1つのペブルを隣接する空の頂点に移動させ、総移動回数を最小化します。最も基本的な離散運動モデルの一つでありながら、ツリー上の複雑性は数十年にわたって未解決でした。さらに、色付きペブル移動に対しては、任意のグラフクラスで初めての困難性結果が得られ、2色でタイトであることが示されました。
これらの結果はすべて、スタック再配置問題（Stack Rearrangement）のNP困難性を証明することによって導かれました。スタック再配置問題は、スタックに格納されたアイテムを最適に再配置するという未解決問題であり、本論文でNP困難であることが示されました。特に、スタックとの関連により、非常に単純なツリー（細分星グラフなど）上でもすべての問題で困難性が得られます。
これらの発見は、複数の基本的な運動モデルに共通する計算上の障壁を明らかにし、以前の困難性結果を統一・強化するものです。この成果は、ロボット経路計画、物流、自動化などの分野に重要な影響を与えると期待されます。