講演名 1998/3/26
Moving-Target Searchの完全性 : 評価関数が非適格な場合
新保 仁, 石田 亨,
PDFダウンロードページ PDFダウンロードページへ
抄録(和) Ishida and KorfによるMoving-Traget Search(MTS)アルゴリズムは目標が変化する状況における実時間ヒューリスティック探索法である.本報告では, MTSの完全性証明法を拡張し, 以下の二つの成果を得た.(1)MTSアルゴリズムの評価値の更新時には現在の値との比較は必要なく, 周辺節点から計算した結果をそのまま代入して良い.(2)たとえ初期評価値が非適格でもMTSアルゴリズムの完全性は保たれる.上記の成果は, 完全性という重要な性質を保ったまま, 用いることのできる評価関数のクラス, ひいてはMTSアルゴリズムの応用範囲を拡げるものである.
抄録(英) We report the following discoveries which we made by extending the completeness proof of the Moving-Target Search developed by Ishida and Korf.・On updating the heuristic values, there is no need to compare(and take the maximum of)the current value with the one computed from the adjacent states.・The completeness is not affected by the use of overstimated(or inadmissible)heuristics.
キーワード(和) 実時間探索 / 変化する目標 / 完全性 / 評価関数 / 問題解決
キーワード(英) Real-time search / moving target / completeness / heuristics / problem solving
資料番号
発行日

研究会情報
研究会 KBSE
開催期間 1998/3/26(から1日開催)
開催地(和)
開催地(英)
テーマ(和)
テーマ(英)
委員長氏名(和)
委員長氏名(英)
副委員長氏名(和)
副委員長氏名(英)
幹事氏名(和)
幹事氏名(英)
幹事補佐氏名(和)
幹事補佐氏名(英)

講演論文情報詳細
申込み研究会 Knowledge-Based Software Engineering (KBSE)
本文の言語 JPN
タイトル(和) Moving-Target Searchの完全性 : 評価関数が非適格な場合
サブタイトル(和)
タイトル(英) The Completeness of Moving-Target Search : When Heuristics Overstimate(Preliminary Report)
サブタイトル(和)
キーワード(1)(和/英) 実時間探索 / Real-time search
キーワード(2)(和/英) 変化する目標 / moving target
キーワード(3)(和/英) 完全性 / completeness
キーワード(4)(和/英) 評価関数 / heuristics
キーワード(5)(和/英) 問題解決 / problem solving
第 1 著者 氏名(和/英) 新保 仁 / Masashi Shimbo
第 1 著者 所属(和/英) 京都大学総合情報メディアセンター
Center for Information and Multimedia Studies Kyoto University
第 2 著者 氏名(和/英) 石田 亨 / Toru Ishida
第 2 著者 所属(和/英) 京都大学大学院工学研究科情報工学専攻
Department of Information Science Kyoto University
発表年月日 1998/3/26
資料番号
巻番号(vol) vol.97
号番号(no) 632
ページ範囲 pp.-
ページ数 8
発行日