芸術科学会論文誌 投稿用カバーシート

■ 論文種類（以下のうちから一つ選択）
  ・原著論文 フルペーパー

■ 論文分野（1)～3)のうちから一つ選択）
  2) 科学系分野

■ カテゴリ（1個以上選択）
  b-3) エージェントシステム

■ 該当特集（以下のうちから一つ選択）
  ・特集名「NICOGRAPH2021発表論文特集」

■ 論文題名(和文、英文)
事前探索データを用いた経路探索手法
Path Finding Method Using Pre-search Data

■ 著者名(和文、英文)
1) 吉田涼真（学生会員）

2) 阿部雅樹（正会員）

3) 渡辺大地 (正会員)

1) Ryoma Yoshida

2) Masaki Abe

3) Taichi Watanabe


■ 著者所属(和文、英文)
1)東京工科大学大学院バイオ・情報メディア研究科
Graduate School of Bionics, Computer and Media Science, Tokyo University of Technology

2,3)東京工科大学メディア学部
School of Media Science, Tokyo University of Technology

■ 著者e-mail
1)g312102830@edu.teu.ac.jp

2)abemsk@edu.teu.ac.jp

3)earth@gamescience.jp

■ 連絡担当者の氏名、住所、所属、電話、Fax、e-mail
氏名: 渡辺大地
住所: 〒192-0982 東京都八王子市片倉町1404-1 東京工科大学メディア学部渡辺研究室
所属: 東京工科大学メディア学部
電話: 042-637-2706
Fax: 042-637-2790
e-mail: earth@gamescience.jp

■ 論文概要(和文400字程度、英文100ワード程度)
経路探索は，ある地点から目的地点への経路を算出するものである．主な手法として，ダイクストラ法や A*アルゴリズムなどがある．この 2 つの手法では，現在の最短経路上から外れた位置に新たな目標地点を設定した際，経路探索を再び行う必要がある．経路探索手法 Moving Target D* Lite は，そのような状態で，マップに変化が生じた際に，最短経路を高速に発見することができる．しかし，この手法は，現在の最短経路上から外れた位置に新たなスタート地点を設定すると成り立たなくなってしまう．本研究は，新規スタート地点や新規ゴール地点を現在の最短経路外に設定した際に先行手法よりも速く新規最短経路を算出可能な探索手法を提案する．提案手法では，ダイクストラ法による探索情報を事前探索データとして複数記録しておき，再探索時にその中から最適なデータを採用し，計算量を削減する．本手法の検証を行った結果，山道のようにほぼ一本道やビル街のように規則的に障害物があるマップに対して現在の最短経路上から外れた位置に新規スタート地点を設定する場合，有用であることが判明した．

Pathfinding is the calculation of a path from a point to a destination point. The main methods are Dijkstra method and
A* algorithm. In these two methods, when a new target point is set outside the current shortest path, the path search
needs to be performed again. The path finding method Moving Target D* Lite can find the shortest path fast under
such conditions and when changes occur in the map. However, this method is no longer viable when a new starting point
is set at a location that is off the current shortest path. In this study, we propose a search method that can calculate a
new shortest path faster than the previous method when a new start point or a new goal point is set outside the current
shortest path. In the proposed method, the search information by Dijkstra method is recorded as multiple pre-search
data, and the optimal pre-search data is adopted from multiple pre-search data . For squares whose cost needs to be
updated based on the pre-search data, the cost is saved as an additional movement cost and the search is performed. As
a result of verifying this method, we found that it is useful when setting a new starting point at a location that is off the
current shortest path for a map that has almost a single path like a mountain road or regular obstacles like a building
district.

■ キーワード(和文5個程度、英文5個程度)
ゲームAI、経路探索、再探索、アルゴリズム、人工知能


※ 投稿原稿はカバーシートをテキストで、本体をPDF形式あるいはWORD形式で
本会事務局にメールにて提出する。本会事務局は受領番号を著者に通知する。
なお、論文本体および付録コンテンツのファイルサイズは原則として、
合計10MB 以内とする。
10MBを超える場合はメールで提出せずに、著者自身のウェブサイト等に
ファイルを置くこと。