Humanoid Autonomous Challengeのような複雑なタスクを完遂する為には，ロボットによる自律的な行動計画が必要です．周囲の状況や自身の状態を鑑みて，どのようにして目標達成に近づいていくかをロボットが判断し，動作の実行順序を選ぶ必要があります．ただ闇雲に歩き回るだけでは，HACの競技目標である「一本道のフィールドでボールに触りに行って，帰ってくる」は達成できないでしょう．
そこで，KXR_HAC_Softwareにおけるロボットの行動計画は，Hierarchical Task Network（階層型タスクネットワーク）を用いて実装されています．
Hierarchical Task Networkの解説
概要
Hierarchical Task Network（以下HTN）は，タスクベースの意思決定アルゴリズムです．目標動作である複雑なタスク（Compound Task）に対して，それを達成するための複数のメソッド（Method）を用意します．このメソッドは，細かい単純なタスク（Primitive Task）の集合です．このように，目標となる動作を単純なタスクの集合に分解することで，樹形状の階層構造が生まれます．
KXR_HAC_Softwareのタスク階層図
このタスク群を最適な順序で実行するために，プランニングが必要です．プランニングでは，周囲の世界の状態（World State）を，各メソッドやタスクに定義された実行条件（Precondition）と実行結果（Effect）と比較しながら，それらの実行順を決定していきます．このプランニング中には，「タスクに定義された実行結果＝このタスクを実行したらこうなっているはずという周囲の世界の状態」を基にして，仮想的なWorld Stateを想定しながら計画を行います．
簡単のために，「ボールに接近して蹴る」というCompound Taskを例にとって説明していきます．
Compound Task「ボールに接近して蹴る」のプランニング
Compound Task：ボールに接近して蹴る
タスクの概要はこのようになっています．ボールに正対していない，かつボールから遠い状態からボールに接近し，脚を振ることでボールを蹴ることを目指します．
タスクの全体構造
これをHTNのタスク構造図にすると，このような形になります．3つのWorld Stateが定義されており，それぞれプランニング開始時にはTrueまたはFalseを保持しています．また，MethodとPrimitive Taskには，実行条件であるPreconditionが定義されています．このPreconditionは，World Stateの状態に紐づいています．さらに，Primitive Taskのみ，実行後に予想されるWorld Stateの変化であるEffectが定義されています．
では，この例について，プランニング開始時のWorld State ①，②，③ が全てFalseであったとします．この時，Preconditionに合致しているMethod「位置調整」がまず選ばれ，その中のPrimitive TaskについてPreconditionとWorld Stateの間で比較が行われます．World Stateは全てFalseのため，Primitive Task「旋回」が行動計画の一つ目に加わります．ここで，Primitive Task「旋回」はWorld State ② をTrueにするEffectをもつため，ここまでプランニングが進んだ段階での仮想的なWorld State ② はTrueになります．
行動計画に「旋回」が加わった後のタスクとWorld Stateの状態
同じMethod内の残りのタスクが探索され，World Stateに合致したPrimitive Task「前進」が計画に加わるとともに，Effectによって仮想的なWorld State ③ もTrueに変わります．
行動計画に「前進」が加わった後のタスクとWorld Stateの状態
World State ②③ がどちらもTrueになったため，PreconditionにしたがってMethod「キック」が選ばれ，Primitive Task「脚を振る」がプランに加わります．EffectによってWorld State ① もTrueになり，全てのWorld StateがTrueになることでプランニングが完了します．
行動計画に「脚を振る」が加わりプランニングが完了した時のタスクとWorld Stateの状態
プランニングが完了したら，そのプランに基づいて実際の動作が実行されます．プランニング時は，前述のとおり仮想的なWorld StateをPrimitive TaskのEffectに従って更新していました．計画を実際に実行する際は，ひとつひとつのPrimitive Taskの実行後に，センサ情報などを用いて実際のWorld Stateを更新します．また，この際，Primitive Task実行後のWorld Stateが，Effectで定義された変化に合致しない場合，そのタスク実行は失敗と判断され，その状態のWorld Stateでもう一度プランニングがし直されます．
タスクの実行
行動計画に基づくタスクの実行について，例えば次のような状態を考えます．先ほど行った行動計画に基づき，Method「位置調整」でロボットがまず旋回を行ったとします．旋回後にセンサを持ちいてWorld Stateを更新したところボールが真正面にあったため，Primitive Task「旋回」は成功したことになり，行動計画における次の項目である，Primitive Task「前進」が実行されました．
行動計画に基づき旋回を実行し，成功
続いて前進を実行するも，失敗
しかしここで，ロボットの足がボールに衝突し，ボールが転がってしまいました．この場合，前進後のWorld State更新でボールが足元に無いことが確認されるため，Effectと合致せず，Primitive Task「前進」は失敗したことになります．行動計画の次の項目であるPrimitive Task「脚を振る」は実行されず，この時点でのWorld Stateを初期条件としてもう一度プランニングが始まります．
このように，HTNを用いたプランニングでは，行動計画をただ実行するだけでなく，World Stateに基づく成功/失敗判定を行うことで，再計画を繰り返して臨機応変に行動することができます．
HTNプランナーの実装
HTNを用いた行動計画は，KXR_HAC_Softwareにおいて主に2つのPythonファイル，HTN_planner.pyとrun_HTN_planner.pyで実装されています．
HTN_planner.py
行動計画のアルゴリズムや，それに関わる各要素の定義が行われていっる核となるファイルです．複数のクラスで構成されています．
class WorldState
World Stateを管理するクラス．World Stateを保持するとともに，更新用の関数を適宜渡すことで，実際の周囲の状況に基づくWorld Stateの更新も行います．
class CompoundTask
Compound Taskを管理するクラス．含まれるメソッドのリストを保持しています．
class Method
Methodを管理するクラス．実行条件であるPreconditionと，含まれるサブタスクのリストを保持しています．
class PrimitiveTask
Primitive Taskを管理するクラス．Preconditionと，実行後に予想される結果であるEffect，実際に実行するアクション（関数）を保持しています．また，WorldStateクラスのインスタンスを渡すことで，Effectと照らし合わせて実行成功/失敗の判断を行います．
class PlanningHistory
プランニングの履歴を管理するクラス．計画の履歴を記録，リセット，復元する機能を持っています．
class FinalPlan
プランニングによって決まった行動計画を保持，実行するクラス．
class Planner
プランニングのアルゴリズムが実装されたクラス．
run_HTN_planner.py
HAC競技目標に合わせて，各メソッドやタスクの詳細な設定を行い，行動計画と実行を繰り返すファイル．KXR_HAC_Softwareは，このファイルを実行することでロボットが動作します．
メインループ以前の設定部分では，World State，Compound Task，Method，Primitive Task，プランナーのインスタンスを生成しています．Compound Task，Method，Primitive Taskは，ひとつのタスク（メソッド）に対してひとつのインスタンスを生成し，Precondition，Effectや実際のアクションを設定することで，プランニングと実行に用いています．その例を以下に示します．（ファイル中から抜粋，加筆）．
####CompoundTaskの設定#### CT_root_task = HTN_planner.CompoundTask("HACStrategy") #HTN_planner.CompoundTaskクラスのインスタンス「CT_root_task」を生成 CT_root_task.set_method(M_find_ball, M_go_touch_ball, M_go_to_goal) #CT_root_taskに含まれるMethodを渡す ####Methodの設定#### M_find_ball = HTN_planner.Method("FindBall") #HTN_planner.Methodクラスのインスタンス「M_find_ball」を生成 M_find_ball.set_precondition(WS_know_ball_pos=False, WS_in_goal=False) #実行条件Preconditionを設定する M_find_ball.set_subtask(PT_init_pos, PT_walk_around) #M_find_ballに含まれるサブタスクsubtaskを渡す ####PrimitiveTaskの設定#### PT_init_pos = HTN_planner.PrimitiveTask("StandUp") #HTN_planner.PrimitiveTaskクラスのインスタンス「PT_init_pos」を生成 PT_init_pos.set_precondition(WS_standing=False, WS_know_ball_pos=False, WS_in_goal=False, WS_touched_ball=False) #実行条件Preconditionを設定する PT_init_pos.set_effects(WS_standing=True) #実行結果Effectを設定する PT_init_pos.set_action(PLANNING.stand_up) #アクションの関数を渡す
おわりに
さて，ここまで書いたように，KXR_HAC_SoftwareではHTN Plannerを実装し，含まれるタスクやメソッドをHAC競技に合わせて設定することでロボットの自律的な行動計画を行っています．
ただ，行動計画とそれに基づく動作を正確に行って競技目標を達成するためには，センサを用いたWorld Stateの正しい取得や，計画に沿った精密かつ安定した移動が必須です．次回の記事では，カメラを用いた外界情報の取得や，ロボットのモーション再生との連携について解説を行っていきます．
