AND/ORグラフによる作業計画 36

2.4. ANDjORグラフによる作業計画 ³⁷

例えば， Fig.2.4に示された組立作業に対して， Table.2.1と Table.2.2に示 されたような作業知識を与える. Table.2.1は， 各部品オブジェクト(PART

OBJECT)に対して与えるPiece及びBaseとなる部品オブジ、エクト名唱を表し，

各クラスに対して記述される. この知識は，操作する部品の順番， すなわち 作業手]11真を決定するために用いられる. また， Table.2.2中の“OPERATION

IN SUBASSEMBLY"は，2つの部品(PAIR OF PARTS)を結合させるための作 業素(メソッド名)を表し， これらの知識は， Pieceオブジ、エクト内に記述さ れる. この知識は， ANDjOR グラフにおけるAND弧に相当する.

目標状態を構成する部品オブジ、エクトが与えられた時， そのオブジ、エク ト間でメッセージの交換を行ない， 前述の各オブジ、エクトに記述された作業 知識(リスト)を連結することで， 組み付け手順に対するANDjORグラフの 解を生成する. この解グラフを基にして作業目標状態を一旦構成し， この 目標状態を入力としAlgorithm Generαte-ANDjOR-Graphを適用することで，

ANDjOR グラフの生成を行なう.

Table.2.1 ， Table.2.2の作業知識によって生成される解グラフはFig.2.10の ようになる.

Pieceオブジ、エクトは， 複数存在しでも良いが， 1つの組立作業ではBase はlつであることを注意しなければならない. もちろん， ここで与えられ る部分組付けの知識は全体として正しい組付け手順を構成しなければなら ないが， ユーザがもっとも理解しやすい手順の入力が行なえるため， 教示 作業に対する負担は軽くなる.

2.4.3 作業プランの探索

ANDjORグラフは， 可能なすべての作業プラン(作業の木)を表現したも のであり， 作業プランは， このグラフを探索することで求められる. この 探索空間の大きさは， グラフを構成するノード， AND弧， ORリンクの数

句PIECE OBJECTS， BASE OBJECTは それぞれ組み付ける部品とその部品に組付け られる部品(の組)を表している. また， ^PIECE OBJECTの順序は， 操作の順番を表して いる.

2.4. AND/ORグラフによる作業計画 ³⁸

。むー奄コ

Fig.2.10: Solntion tree corresponding to Table.2.1

2.4. AND/ORグラフによる作業計画

Table.2.1: A le of knowleclge fo1' Fig.2.1 I PART OBJECT

11

^PIECE

OBJECTS I

BASE OBJECT

I

Armature ^NIL Shaft

Shaft A1'matu1'e Housing

Housing (Shaft Co^ve^r) NIL

Cove^{r NIL} Housing

Table.2.2: The operations in subassembly listed in Table.2.1 PAIR OF PARTS I OPERATION IN SUBASSEMBLY (base-object piece-object)

(Sh^aft Armature) (Housing Shaft) (Housing Cover)

P LACE-INTO-TUBE P LACE-INTO-TUBE

PLACE-ON

39

によって決定さる. ある目標対象物 が与えられた時のそのグラフの大きさ (可能な作業プランの数)Num(t)は，

I

^{1 if t == (η) 01' t ニ(nln2)}

urn(t) ==

<

l

n(tl)仰2)ぷYU:)!otherwise

で， 決定される. ここで， 札口1，口2 は，ノード (部品オブジ、エクト)を表し，

t == (nln2)はnl， n2をノードに持つグラフを表している. また， 関数α(t)は，

α(t)==pα山(t)- 1

であり，parts(t)は，そのグラフ が構成する 部品の数を表している. したがっ て，前節で示した，作業に対するグラフの大きさは， 6となる. また，Fig.2.11 で示されたようなAからKまでラベルづけされた11個の部品からなる構

成物に対するAND/ORグラフは， 75のノード(部分組み付け状態)と221の AND弧を持ち， その大きさは， 3319となる.

2.4. ANDjORグラフによる作業計画 40

Fig.2.11: Salnple asselnbly product which consists of 11 parts.

この ように， 構成部品の増加にともないその探索領域は非常に大きく なる. したがって， 効率の良いグラフ探索法が必要である. このAND/OR グラフの探索には， 問題解決でよく用いられるヒューリスティック関数を用 いたグラフ探索を行なう. 作業プラン生成のためのグラフ探索アルゴリズ

ムをFig.2.12に示す.

Algorithm ANDjOR-GTaph-SeaTch(t)

このアルゴリズ ムは， 目標状態 のAND/Ollグラフを入力とし， 各部分 組み付け状態の持つヒューリスティック関数を計算することで最適なグラ フ探索を行なうものである. まず， 目標状態を表すノードの可能な組み付 け(AND弧)とその組み付けの 評価値を求め， OPEN変数に代入する. 次 に， OPEN変数 の中のAND弧の中で評価値が最小のものをSOLUTIONに 入れ ， OPENの内容をクリアする(Best百、ee関数). SOLUTIONの中で終端節

2.4. ANDjORグラフによる作業計画

procedure ANDjOR-Graph-Seαrch( t);

begin

41

OPEN←{ ノードtを構成するための2進木の列とそれら評価値};

until ^empty( 0 P E N) do begin

SOLUTION←B estTree( 0 P E N)

if { SOLUTIONの終端節点(Terminal node)が分解不可能}

return SOLUTION ;

SUCCESSOR←{SOLUTIONの終端節点が 1つの部品で構成されていないもの};

for { SUCCESSORの要素n} do begin

h← { nのヒューリスティック値を計算};

p1川(h， H);

end;

pωh(BEST(H)， SOLUT ION);

OPEN←{BEST(H)に対応するノードを構成するための 2進木の列とそれらの評価値};

end;

return FAIL;

end{ Generαte-A N D j 0 R-Graph}

Fig.2.12: The algorith to gene川e an asselubly plan using an AND jOR graph

2.4. ANDjORグラフによる作業計画 42

( Tenninal N ode)となっている状態が1つに部品から構成されていれば(終端 節点の状態を表す2進木をtとするとNum(t)⁼⁼ 1)， SOLUTIONを作業プラ ンとして， 処理を終る. そうでないとき， SOLUTIONの終端節点の中で分 解可能なノードn (Num(n)ヂ1) のすべてについて， 状態 nを構成するため のヒューリスティックhを算出する. hの中でもっとも評価の小さいものに 対応する， 状態ノードとその評価値を SOLUTIONに加える(BEST関数 ). さ らに， OPENにこのノードと評価値を代入して， 全体を繰り返す.

このアルゴリズムで， 最適な作業プランを生成するためには， 各ノー ドにおけるヒューリスティック関数をうまく決める必要がある. ここでは，

その評価として， 各状態ノードにおけるグラフの大きさ， とその状態ノー ドを達成するまでの作業素の難易度を用いている. 状態ノードのグラフの 大きさとは， その状態を根(root)とした場合のグラフηにおけるNum(η)で あり， そのノード以下のグラフの深さである. いま， Num(n) <α(n) が成立 する時， この作業が並列的に実行することができることを示している. ま た， Fig.2.7で定義した基本作業素に応じて， 作業の難易度Dを定義する.

ここでは， 組み付け作業を面と面との接触または， HOLEと 操作対象部と の配置を決定することと仮定している. そこで 作業の難易度Dを組み付 けの作業を行なった時ときの操作される部品が掃引された領域(これを単 に掃引領域と呼ぶ) によって決定する. すなわち， Fig.2.13に示されたよう なPLACE-ON作業に対しては， 作業操作に対する掃引領域 Sweepの組み付 ける部品への正射影をあ， 踏みつける領域の面積Sによって

掃引領域の断面積Sl 作業の難易度DP [，t'LA ω UAí: P，οN -IV一操作対象 物 :‘ 一ー

として定義する. また， HOLEとの組み付け作業(Fig.2.14参照)PLACE-INTO，

PLACE-INSIDEではDpLACE-ONに，組み付けるHOLEの深さと操作部品の長 さの比を乗じたものを用いる. また，DpLACE-INTO，PLACE-JNSIDEはhUOl.，E二O

2.4. AND/ORグラフによる作業計画

Operaling Direclion

Fig.2.13: Di伍culty of an asselnbly operation(PLACE-ON)

43

の時， DpLACE-INTO，PLACE-INSIDE = DpLACE-ONとなるようにする. すなわち，

St (

HOLEの深さlIIOLE

λ

DpLACE-川、0，円ACE-INSIDE 二百

〔

操作対象物の 挿入方向の 長 さ

Z; T J.)

と定義する.

このように定義された難易度Dは， 操作作業は容易なほど小さな値を持 つ. この難易度は， 同じ大きさの面同士をの接続させる操作を1としたもの であり. 難易度D= 0は， 接続させる平面が存在しない状態を表し， D=∞

は， すべての面に接続操作を行なうことができることを示している.

2.4. AND/ORグラフによる作業計画 ⁴⁴

Operating Direction

Fig.2.1凶4: Di伍Cl山y of ^an assembly ope川io叫PLACE-INTO，PLACE-INSIDE)

ドキュメント内 マニピュレータの動作を考慮した組立作業プランニ ングに関する研究 (ページ 42-51)