実用的な経路計画生成のための時間制約付きヒューリスティック探索

• Item type: Journal(1)
• 公開日: 1999-11-15
• タイトル: 実用的な経路計画生成のための時間制約付きヒューリスティック探索
• タイトル / 言語: en
• タイトル: Time - constrained Heuristic Search for Practical Route Finding
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 論文
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• その他タイトル / その他のタイトル: 知識処理
• 著者所属: 東京理科大学理工学部
• 著者所属: 東京理科大学理工学部
• 著者所属: 東京理科大学理工学部
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Science University of Tokyo
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Science University of Tokyo
• 著者所属(英): en
• 著者所属(英): Faculty of Science and Technology, Science University of Tokyo
• 著者名: 平石, 広典; 大和田, 勇人; 溝口, 文雄
• 著者名(英): Hironori, Hiraishi; Hayato, Ohwada; Fumio, Mizoguchi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 指定された時間内に準最適な経路を求めるヒューリスティック探索アルゴリズムを提案する．このアルゴリズムは従来のε?近似によるA＊を基本にするが，探索中にεの値を動的に変化させることで制限時間に間に合うように探索を終了させることができる．出発点に近いノードは厳密に探索し，目的地点に近いノードはεの値を増加させて粗く探索する．これは移動中の走行車におけるリアルタイムな経路生成に適したものである．カーナビなどで使用される実際のデジタルマップを用いて本アルゴリズムを適用し，アルゴリズムの特徴を実験的に明らかにした．その結果，探索の終了時刻を正確に推定することができ，制限時間を十分に利用しながら最適な解が得られることが分かった．さらにこの特徴はマシンの性能に関係なく成り立つもので，本方法は汎用なリアルタイム経路探索になっている．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper,we describe a heuristic search algorithm that finds a provably optimal solution subject to a specified time interval.While this algorithm is amenable to previous works on an approximate A* search with a bounded error(ε),it allows us to terminate the search to retain the specified time interval by changing the value of ε during the search.Our basic search strategy is that node expansion around the starting node is pessimistic(exact search),and we accomplish the approximate exploration of nodes around the goal by increasing ε.This strategy is suitable for real-time route finding in automobile navigation systems.We conducted our experiments to clarify the practical features ofthe algorithm,using a digital map of a commercial automobile navigation system.The resulting advantage is that the estimation of the finishing time of the search is quite accurate,and optimal solutions are produced by making full use of the permissible search time,regardless of different machine performances.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 40, 号 11, p. 4021-4029, 発行日 1999-11-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764