中間目標を用いた双方向探索の導入によるSTRIPSの効率化について
スポンサーリンク
概要
- 論文の詳細を見る
STRIPS is well known as one of unidirectional search algorithms in which the search tree is rooted at the goal. In order to avoid the defect, the number of nodes in a search tree grows exponentially with its depth, of STRIPS like some other unidirectional algorithms, many improved algorithms have been proposed. Here we would furthermore introduce a new efficient bidirectional heuristic search algorithm into STRIPS to make its search more efficient. We would like call our new algorithm Bi-STRIPS. Being different from other bidirectional heuristic searches, the forward search, from the initial state, and the backward search, from the goal, of Bi-STRIPS both aim at a set of nodes between the initial state and the goal. Those nodes are called middle goals and any solution path must go througth one of them. By utilizing this kind of bidirectional heuristic search, the two search trees not only will expand less nodes than STRIPS but also can be expanded parallely, and the search time for planning can be reduced. Therefore, efficiency of planning can be improved. We would call an element of a state destructive element if it can be deleted by applying a production rule to the state. Surfacing an element of a state means to search for a new state in which the element will get to be a destructive element. We would call those elements of a state differences between that state and a subgoal if they cannot exist with the subgoal at the same time. A middle goal is such a state in which every element of differences between that state and the present subgoal is surfaced. The forward search tree of our algorithm is a destructive one because a node contains no less surfaced elements than its ancestors. In this paper, we will describe the deduction process of the middle goals and show the algorithms of the main parts of Bi-STRIPS. Some examples also will be shown to clarify the efficiency of our system.
- 社団法人人工知能学会の論文
- 1992-07-01
著者
関連論文
- 正則化による複数距離画像の統合及びその3次元モデリングへの応用
- 統計モデルを用いた輪郭特徴と3次元曲面の再構成
- 曲面特徴の一貫性に基づく弛緩法による三次元形状復元
- 群知能ロボット総論
- ロボット言語
- 2台のカメラとレーザスリット光投光器を用いたレンジファインダの試作とそのキャリブレーション
- 異種ビジュアルセンサを組み合わせたアクティブビジョンシステムとそのパーツピッキングへの応用
- 複雑に重なって見える柔軟対象物体の3次元姿勢決定
- 曲面パッチに基づく画像記述を利用した三次元曲面物体の認識
- 基本曲面パッチの集合による画像の記述
- ガウス写像における曲面の姿勢パラメーターを推定する方法について
- Configuration 空間における障害物記述に関する考察
- 視点集合の演算によるアスペクトグラフの生成
- ビジュアルフィードバック手法を利用した配電線工事における電線把握システムに関する研究
- ジョイント・マップを用いたマニピュレ-タの衝突回避経路の生成
- 球面画像上でのオプティカルフロー計算
- 球面画像を考慮した六角形画素チェイン符号化法
- 球面六角形画像ピラミッドを用いた球面投影による全方位画像処理
- メタ知識を利用したプランニングシステム
- 曲面の微分特徴量の抽出と法ベクトル図の分割
- メタ知識を利用したプランニング
- ももち地区に新スポット誕生
- 中間目標を用いた双方向探索の導入によるSTRIPSの効率化について
- プランニングにおける連接的目標処理の一手法 : 時間推論による順序関係の導出について
- プランニングの効率化の一手法 : 関連規則の導出について
- Research trends on off-line programming of robots.
- ロボットはどこまでヒトに近づけるか
- ロボット研究の今後の課題
- ロボットにおけるプランニング問題
- 組立作業手順計画
- 自律分散システムと情報処理 (自律分散システム) -- (自律分散システムの現状と課題)