講演名 | 1996/1/18 重み付き実時間探索 新保 仁, 石田 亨, |
---|---|
PDFダウンロードページ | PDFダウンロードページへ |
抄録(和) | 実時間探索アルゴリズムLBTA*の一つの特徴は学習機能にある。推定評価関数が適格な場合、問題解決を繰り返すことにより、最終的に問題解決器のたどる経路は最適解へと収束することが知られている。本稿では、推定評価関数が非適格の場合の解の収束について考察する。結果として、推定評価関数が正確なコストの(1+ε)倍以内のとき、LRTA*は誤差が最適解のε倍以内の準最適解に収束することが解析的に得られる。また、非適格な評価関数を用いることで、収束までの時間が軽減しうることを、迷路の例を用いて実証する。 |
抄録(英) | We discuss how the realtime search algorithm LRTA* is affected by inadmissible initial heuristic function. The proof is presented that when heuristic function overestimates the actual cost by at most a factor of 1 + ε, the cost of the paths traversed by LRTA* after convergence will not be worse than the optimal one by a factor greater than 1 + ε. |
キーワード(和) | 実時間探索 / 学習 / 評価関数 / 間題解決 |
キーワード(英) | Realtime search / learning / heuristic evaluation function / problem solving |
資料番号 | AI95-43 |
発行日 |
研究会情報 | |
研究会 | AI |
---|---|
開催期間 | 1996/1/18(から1日開催) |
開催地(和) | |
開催地(英) | |
テーマ(和) | |
テーマ(英) | |
委員長氏名(和) | |
委員長氏名(英) | |
副委員長氏名(和) | |
副委員長氏名(英) | |
幹事氏名(和) | |
幹事氏名(英) | |
幹事補佐氏名(和) | |
幹事補佐氏名(英) |
講演論文情報詳細 | |
申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
---|---|
本文の言語 | JPN |
タイトル(和) | 重み付き実時間探索 |
サブタイトル(和) | |
タイトル(英) | Weighted Realtime Search |
サブタイトル(和) | |
キーワード(1)(和/英) | 実時間探索 / Realtime search |
キーワード(2)(和/英) | 学習 / learning |
キーワード(3)(和/英) | 評価関数 / heuristic evaluation function |
キーワード(4)(和/英) | 間題解決 / problem solving |
第 1 著者 氏名(和/英) | 新保 仁 / Toru Ishida |
第 1 著者 所属(和/英) | 京都大学 工学部 情報工学教室 Department of Information Science, Kyoto University |
第 2 著者 氏名(和/英) | 石田 亨 / Masashi Shimbo |
第 2 著者 所属(和/英) | 京都大学 工学部 情報工学教室 Department of Information Science, Kyoto University |
発表年月日 | 1996/1/18 |
資料番号 | AI95-43 |
巻番号(vol) | vol.95 |
号番号(no) | 460 |
ページ範囲 | pp.- |
ページ数 | 8 |
発行日 |