| 講演名 | 1998/9/24 多状態コミットメント探索の性能評価 宮地 智久, 北村 泰彦, 横尾 真, 辰巳 昭治, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 準最適解を求めるヒューリスティック探索の高速化手法の1つである多状態コミットメント探索の性能が問題のどのような性質に依存しているかを解明する.15パズル問題, ハノイの塔問題, 迷路問題におけるMSC-RTA^*とRTA^*の動作を比較し, 直列化可能な副目標を持つ問題や, 同じ評価値を持つ状態が密集した領域を持つ問題ではMSC-RTA^*がRTA^*以上に性能を発揮できることを示す.また, MSC-WA^*がWA^*より良い性能を示すのは一時的な刈り込みのためであり, 刈り込みが有効な問題ではMSC-WA^*がWA^*より少ない展開数で解が得られることを示す.最後に, そのような性質を持つ3つの人工モデルを作成し, シミュレーション実験によって検証を行う. |
| 抄録(英) | We analyze Multi-State Commitment(MSC) Search algorithms which are heuristic search algorithms for semi-optimal solutions. We compare MSC-RTA^* with the original RTA^* on 15-puzzle, tower of hanoi, and maze problems, and show that if a problem has serializable subgoals, or a stage-space graph which have states with identical heuristic values, MSC-RTA^* can show superiority over RTA^*. We then show that NSC-WA^* can find solution with fewer state expansions than original WA^* on the problems in which cutting branches is effective. Finally, we make three artificial models with these properties espectively, and verify the performance by experiments on the models. |
| キーワード(和) | ヒューリスティック探索 / コミットメント / 準最適解 |
| キーワード(英) | heuristic search / commitment / semi-optimal solution |
| 資料番号 | AI98-37 |
| 発行日 |
| 研究会情報 | |
| 研究会 | AI |
|---|---|
| 開催期間 | 1998/9/24(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Artificial Intelligence and Knowledge-Based Processing (AI) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 多状態コミットメント探索の性能評価 |
| サブタイトル（和） | |
| タイトル（英） | Performance Analysis of Multi-State Commitment Search |
| サブタイトル（和） | |
| キーワード(1)（和/英） | ヒューリスティック探索 / heuristic search |
| キーワード(2)（和/英） | コミットメント / commitment |
| キーワード(3)（和/英） | 準最適解 / semi-optimal solution |
| 第 1 著者 氏名（和/英） | 宮地 智久 / Tomohisa MIYAJI |
| 第 1 著者 所属（和/英） | 大阪市立大学工学部情報工学科 Dept.of Information and Communication Engineering, Faculty of Engineering, Osaka City University |
| 第 2 著者 氏名（和/英） | 北村 泰彦 / Yasuhiko KITAMURA |
| 第 2 著者 所属（和/英） | 大阪市立大学工学部情報工学科 Dept.of Information and Communication Engineering, Faculty of Engineering, Osaka City University |
| 第 3 著者 氏名（和/英） | 横尾 真 / Makoto YOKOO |
| 第 3 著者 所属（和/英） | NTTコミュニケーション科学研究所 NTT Communication Science Laboratories |
| 第 4 著者 氏名（和/英） | 辰巳 昭治 / Shoji TATSUMI |
| 第 4 著者 所属（和/英） | 大阪市立大学工学部情報工学科 Dept.of Information and Communication Engineering, Faculty of Engineering, Osaka City University |
| 発表年月日 | 1998/9/24 |
| 資料番号 | AI98-37 |
| 巻番号（vol） | vol.98 |
| 号番号（no） | 296 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |