直交部分観測協調ガードアートギャラリー問題における最適コーナー選択の学習

本論文は、Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP) を解く CADENCE アルゴリズムにおいて、各エージェントをどの有効な corner に配置するかを学習する2つのヒューリスティックを提案する。1つは grid encoding 上で候補を評価する CNN、もう1つは visibility graph 上で Deep Q-Learning (DQN) により訓練する GATv2 ネットワークである。これらは CADENCE の形式的な coverage と connectivity の保証を維持したまま、効率を改善することを目的とする。

- CADENCE は POCGAGP を形式的保証付きで解くが、どの corner に各エージェントを配置するかは未指定であり、効率に大きく影響する。 - 提案手法はこの corner 選択を学習により改善し、形式的保証を損なわない。 - 7,500 回のランダム直交環境 (50x50 から 250x250) の実験で、baseline CADENCE より full coverage までの steps と peak agent count の両方で優れ、規模が大きいほど利得が増大する。 - Incremental Self-Deployment (ISDA) ベースラインと比べ、agent utilization を改善しつつ、ISDA に欠ける保証を提供する。

- 2つの学習ベース corner 選択ヒューリスティックを導入。 - 1つ目は CNN で、grid encoding 上で候補 corner をスコアリングする。 - 2つ目は GATv2 ネットワークで、visibility graph 上で Deep Q-Learning (DQN) により訓練する。 - いずれも CADENCE の形式的な coverage と connectivity の保証を保持する。

- ランダムな直交環境 (50x50 から 250x250) で 7,500 回の実行を行った。 - 評価指標は full coverage までの steps と peak agent count。 - 提案ヒューリスティックは baseline CADENCE を両指標で上回り、規模が大きいほど利得が増大した。 - Incremental Self-Deployment (ISDA) ベースラインと比較し、agent utilization を改善しつつ、ISDA にない保証を提供することを示した。

- 学習された corner 選択は CADENCE の速度と agent utilization を改善し、形式的性質を損なわない。 - 利得は環境規模の増大とともに大きくなる。 - 具体的な限界や失敗ケース、計算コスト、一般化性に関する議論は要旨からは不明。

- CADENCE (本論文のベースライン) - Incremental Self-Deployment (ISDA) - GATv2 - Deep Q-Learning (DQN) - Partially Observable Cooperative Guard Art Gallery Problem (POCGAGP) 関連の定番研究