最短経路探索問題のための動的計画法へのコスト平準化の指標の適用

• 松井, 俊浩

• マリウス, シラギ

• 平山, 勝敏

• 横尾, 真

• 松尾, 啓志

書誌事項

タイトル別名

• Applying Criterion of Leveling of Costs to Dynamic Programming for Shortest Path Finding Problems

抄録

最短経路探索問題はエージェントの行動決定における基礎的な問題である．従来の問題では，最適経路は部分経路の合計コスト値が最小となる経路として定義され，解法として動的計画法が用いられる．本研究では，経路全体の最大コスト値を改善し，かつコストを平準化することを目的とする経路最適化問題に注目する．このような問題は，各部分経路の近隣住民の不満や施設の消耗の程度を考慮する状況と関係し，実際的な要求を考慮する解のある種の下界を与える点で一定の重要性があると考えられる．このために，多目的最適化問題において公平性を重視するleximinに類する指標を，最短経路探索問題のための動的計画法に適用する．まず，この指標に基づきA*探索アルゴリズムを拡張した解法を提案し，その効果を実験的に評価する．また，未知の環境に適用可能な，探査と学習に基づくインクリメンタルな解法の可能性について考察し，下界に基づく探査を行うオンライン型探索アルゴリズムを直接的に拡張することが困難であることを示す．そして代替案として，探査と学習の段階を繰り返すエピソードに基づく学習に発見的な手法を適用し，完全な知識に基づくA*探索アルゴリズムと同等の解に収束しうることを実験的に示す．

Shortest path finding problems are fundamental to behavior-decision processes of agents. In traditional problems, the optimal path is defined as having the minimum total cost value among partial paths. To solve such problems, dynamic programming methods are employed. We focus on the cases where the objective of path optimization is the minimization of the worst-case cost and the leveling of costs among partial paths. Issues considered include the penalty from the complaint of each resident and the lifetime of each facility on partial paths, whose lower bound will be important information in practical problems. To this end, we apply an egalitarian criterion that resembles leximin to dynamic programming methods for shortest path finding problems. We first address the path optimization problem with the new criterion employing a variant of the A* algorithm and empirically evaluate the effect of the algorithm. Then, for unknown environments, the opportunity to develop incremental search methods based on exploration and learning is also investigated and we show that it is hard to directly generalize an existing online search algorithm with the new criterion. Instead of that, we employ an episode-based learning algorithm with heuristic approaches and experimentally show that the proposed solution method is able to achieve the same quality of the solution which is obtained by the extended A* algorithm.

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 60 (10), 1603-1616, 2019-10-15

キーワード

• [特集：エージェント理論・技術とその応用] 公平性，動的計画法，A*，最短経路問題

詳細情報

• CRID: 1050282813791880576
• NII論文ID: 170000180523
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00199625/
• 本文言語コード: ja
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN