🐵B.2 Behavior Trees

Navigation 2 ကို သေချာ မသိသေးရင် ဒါကို ခန ကျော်သွားလို့ရပါတယ်။

BEHAVIOR TREE

Introduction

Robotics ကိုလေ့လာရမှာလက်ရှိ ros2 technique တွေထဲက behavior treeလေ့လာပါမယ်။ သူ့ကို မလေ့လာမီ အရင် နည်းပညာဖြစ်တဲ့ Finite State Machine ( FSM ) ကို အရင်လေ့လာ ကြည့်ရအောင်။ FSM မှာက ဆက်တိုက် ဆောင်ရွက်ဖို့ အချက်အလက်တွေရှိတယ်ဗျ။ ဥပမာ

ကျတော်တို့ ကွန်ပြူတာမှာ ဖွင့်/ပိတ် ဆိုတဲ့ state နှစ်ခုရှိတယ်။ ဒါသည် state machine တစ်ခုပဲပေါ့။ ဖွင့် တာပဲ ဖြစ်ဖြစ် ပိတ်တာပဲဖြစ်ဖြစ် state တစ်ခုသည် input button နဲ့ previous state ပေါ်မှီခိုနေပါတယ်။ ဒါကြောင့်ပဲ ဆက်တိုက်ဖြစ်တဲ့ sequential လို့ခေါ်တာပေါ့။ ( more details အကျယ်သိချင်ရင်တော့ ရှာဖတ်ပေါ့ )

ပုံမှာဆိုရင်တော့ FSM နမူနာပေါ့။ robot ဟာ

ဘောလုံးရှာမယ်။

ဘောလုံးနားကို သွားမယ်။

ဘောလုံးကို ကိုင်ယူမယ်။

အမှိုက်ပုံးနေရာကိုသွားမယ်။

အမှိုက်ပုံးထဲ ထည့်မယ်။

ပြီးရင် နောက်တခါ loop ပတ်ပြီး ပြန်လုပ်မှာဖြစ်ပါတယ်။

အဲ့တော့ ဒါသည် finite state machine တစ်ခု ဖြစ်ပြီးတော့ sequential လဲဖြစ်ပါတယ်။ ဆိုခဲ့သလိုပဲ state machine တစ်ခုမှာ finite states အခြေအနေများပါဝင်ပြီး ဆက်တိုက်ဆောင်ရွက်ရမှာဖြစ်ပါတယ်။ current state တို့သည် previous state နဲ့ input ပေါ်မှာမူတည်ပါတယ်။ input ဆိုတာက sensor ပေါ့။

ဒီဥပမာမှာဆိုရင် robot က ဘောလုံးကိုတွေ့ရင် အနားကိုသွားမယ် ကောက်ယူမယ် အမှိုက်ပုံးနားသွားမယ် ပုံးထဲထည့် မယ် ဒီ process ကိုပဲ ထပ်ကာတလဲလဲလုပ်နေမှာဖြစ်ပါတယ်။ ဒီ process မှာ fault တစ်ခုဖြစ်သွားရင် အကူအညီတောင်းသည့် ဖြစ်စဥ်ရှိဖို့လိုအပ်ပါတယ်။

FSM ရဲ့ ပထမအားနဲချက်အနေနဲ့ robot ရဲ့ လက်ထဲက ဘောလုံး ကို ဖယ်ထုတ်လိုက်ရင် robot က သိမှာမဟုတ်ပါဘူး။ ဒီဖြစ်စဥ်မျိုးအတွက် state တွေထပ်သုံးပြီး ဖြေရှင်းလို့ရပေမဲ့ robot သည် ဒီလို case တွေအတွက် intelligence မဖြစ်ရင် မလွယ်ပါဘူး။ ဒါကြောင့် FSM သည် reactive မဖြစ်ဘူးလို့ပြောနိုင်တယ်။

နောက်တချက်ကတော့ ဘောလုံးကောက်တဲ့ ဖြစ်စဥ်ကို တခြားနေရာမှာ နောက်တခါပြန်သုံးချင်ရင် သုံးလို့မရဘူး။ ဒါသည်လဲ Modularity မဖြစ်ဘူးလို့ဆိုရမယ်။ ဆိုတော့ system ဟာ simple system ဖြစ်မှသာ finite state ကို သုံးသင့်ပါတယ်။ System ဟာ complex ဖြစ်ရင်တော့ finite state ကို အသုံးမပြုသင့်ပါဘူး။

Behavior Tree

သူ့ကို မလေ့လာခင် သူ့မှာသုံးတဲ့ timing ကိုသိထားဖို့လိုတယ်။ tick ဆိုတဲ့ signal ကို parent node ကို ပေးလိုကတာနဲ့ tree တခုလုံးရဲ့ leaf node တွေရောက်သည်အထိ tick signal ကို ဆက်ပို့ဆောင်သွားမှာ ဖြစ်ပါတယ်။ တနည်းအားဖြင့် timing ပါပဲ။ သို့ပေသိတစ်ခုတော့ ရှိတယ်။ tick ရတဲ့ကောင်သည် reply ပြန်ရမယ်။ reply ပြန်ရမယ့် state က ၃ခု ရှိပါတယ်။

• SUCCESS

• FAILURE

• RUNNING

ဒီ ၃ ခုထဲက တခုကို Return ပြန်ရမှာဖြစ်ပါတယ်။ ကဲ စလိုက်ကြရအောင်။

ဒါကတော့ behavior tree ပေါ့။ သူ့မှာ အနီနဲ့ပြထားတဲ့ control flow node ရယ် အစိမ်းနဲ့ပြထားတဲ့ leaf node တွေပါဝင်ပါတယ်။ leaf node ကို execution node လို့ခေါ်ပါတယ်။

Behavior Tree တစ်ခုကို execute လုပ်တဲ့အခါ root node ကစပါတယ်။ node တွေသည် tick လို့ခေါ်တဲ့ အချက်ပြမှုတခုကို ရရှိမှသာ execute လုပ်ရပါတယ်။ root node သည် tick ကို ထုတ်လုပ်ပြီး child node တွေ ဆီပါဆက်လက်ပို့ဆောင်ပါတယ်။ BT သည် node တွေကို execute လုပ်ရာတွင်လည်း left to right သာ လုပ် ဆောင်ပါတယ်။ Node တွေကို ယျေဘူယျအားဖြင့် ၄ မျိုးမှတ်ထားနိုင်ပါတယ်။

Sequence node → သူက child nodes တွေကို left မှ right သို့ run ပါတယ်။ child node တွေအားလုံး success return ပေးပါမှ sequence node သည် parent ကို success return ပြန်ပါတယ်။ sequence

node ရဲ့ ပထမဆုံး child node run နေတဲ့အချိန်ကစပြီး sequence node သည် running ပြနေမှာ ဖြစ်ပြီး နောက်ဆုံး child node success ဖြစ်မှာ parent ဖြစတဲ့ sequence node လဲ success ဖြစ်ပါတယ်။

Fallback node → သူကလည်း sequential node လိုပါပဲ။ ဒါပေမဲ့ child node တွေကို run ရာမှာ child တွေရဲ့ return အဖြစ် success, running တခုခုကို မရသေးသရွေ့ run ပါတယ်။ child တစ်ခုက Failure return ပြန်ရင် next child node ကို tick ပေးပြီး run စေပါတယ်။ Child ရဲ့ return က success ဖြစ်ရင်တော့ နောက်ထပ် child တွေကို ဆက် မ run တော့ပါဘူး။ children အားလုံးက Failure return ပေးရင်တော့ Fallback node ကလဲ Failure return ပဲ ပြန်ပေးပါတယ်။ ဒါကြောင့် fallback node တွေကို selector node တွေလို့လည်း ခေါ်ပါတယ်။ Control Node တွေဖြစ်တဲ့ sequence node နဲ့ fallback node တွေပါတဲ့ tree ကို လေ့လာကြည့်ပါအုံး။

Sequence node ကနေ ဘယ်ဘက် Fallback ကိုရောက်မယ်။

Fallback မှာ တံခါးဖွင့်ထားရင် Enter Room ဘက်သွားပါမယ်။

မဖွင့်ထားရင် openDoor ကို ဆက်သွားမယ်။

OpenDoor က Failure ဖြစ်ရင် Sequence Node ဘက်သွားပြီး အစဥ်အတိုင်း ပါမယ်။

Sequence Failure ဖြစ်ရင်လည်း တံခါးကို ရိုက်ဖွင့်ပါမယ်။

ပီးမှ Enter Room ကို ဆက်သွားမယ်ပေါ့။

Parallel node → သူကျတော့ child node တွေအကုန် run မှာဗျ။ ဒါပေမဲ့ user က သတ်မှတ်ထားတဲ့ node အရေအတွက် တွေ success ဖြစ်ရင် သူလဲ success ပေါ့။ success ဖြစ်တဲ့ node အရေအတွက်သည် သတ်မှတ် အရေအတွက်ထက်နဲရင်တော့ failure ပေါ့။

Decorator node → သူ့မှာက child တစ်ခုပဲရှိမယ်။ child node တွေကို အချိန်ဘယ်လောက်ပေးရမလဲ တနည်းအားဖြင့် tick ဘယ်လောက်ပေးရမလဲဆိုတာကို decorator node က ဆုံးဖြတ်ပါတယ်။

Execution node → သူ့မှာတော့ နှစ်မျိုးရှိပါတယ်။ Action node နဲ့ Condition node ပေါ့။ Action node ကတော့ action တစ်ခုကို ဆောင်ရွက်ပေးနိုင်ပြီး return အနေနဲ့ success, running, failure တခုခုပြန်ပေးမှာပါ။ condition node ကတော့ condition ကို စစ်ဆေးပြီး success, failure တခုခု အကြောင်းပြန်မှာပါ။

ပုံမှာကြည့်ရင် root node သည် fallback node ဖြစ်ပြီး tree ရဲ့ ဘယ်ဘက်ခြမ်း node ကို အရင် run မှာဖြစ် ပါတယ်။ ညာဘက်ခြမ်းသည် ask for help node ဖြစ်ပါတယ်။ ဘယ်ဘက်ခြမ်းက success သို့မဟုတ် running ကို return ပြန်ပေးမယ်ဆိုရင် ညာဘက်ခြမ်းဖြစ်တဲ့ ask for help node ကို run စရာမလိုတော့ပါဘူး။

Root node ရဲ့ ဘယ်ဘက်ခြမ်း node သည် sequence node ဖြစ်ပြီး child node များကို တစ်ခုပြီးတစ်ခု tick ပေးပြီး run ခိုင်းမှာဖြစ်ပါတယ်။ သူ့ရဲ့ child တွေအားလုံး success ဖြစ်ရင် sequence node လည်း success ဖြစ်မှာဖြစ်ပြီး သူ့ရဲ့ node တစ်ခုက failure ဖြစ်တာနဲ့ sequence node လည်း failure ဖြစ်ပြီး ask for help ကို ရောက်သွားမှာဖြစ်ပါတယ်။

နောက်တခါ sequence node ရဲ့ အောက်မှာ fallback node ရှိပြီး left child node ဖြစ်တဲ့ ball found က fail ရင် right child node ဖြစ်တဲ့ find ball ကို run ပါမယ်။ ဒီနေရာမှာ ball found သည် condition node ဖြစ်ပြီး find ball သည် action node ဖြစ်ပါတယ်။ ဘောလုံးကိုတွေ့ရင် success return ပေးမှာဖြစ်ပြီး fallback node ဆီ ပြန်ရောက်သွားမယ်။ သူကတဆင့် sequence node ကို ပြန်ရောက်သွားမှာဖြစ်ပြီး နောက်တစ်ဆင့်ကို ဆက်သွား ပါမယ်။

တကယ်လို့ ဘောလုံးကိုသာ မတွေ့ခဲ့ဘူးဆိုရင်တော့ Find Ball ကို run မယ်။ Find Ball က running ဖြစ်နေရင် parent node ကလည်း running ဖြစ်နေမယ်။ ဆိုလိုတာကတော့ system တစ်ခုလုံးသည် running ကို စောင့်နေရ မှာဖြစ်ပါတယ်။ success or failure အဖြေသိရသည်အထိပေါ့။ Find Ball မှာ ball found condition ကို စစ်ပြီး ဘောလုံးကိုတွေ့ခဲ့ရင်တော့ success return နဲ့ sequence node ကနေတစ်ဆင့် Ball close ကို ဆက်သွားမှာဖြစ်ပါတယ်။

Ball close နဲ့ တခြား fallback node တွေကလည်းဒီပုံစံပါပဲ။

ဒီမှာ reactivity က ဘာကိုပြောတာလည်းဆိုတော့ robot သည် ဘောလုံးကောက်ပြီး bin ဆီသွားနေတယ်ဆိုပါစို့။ တယောက်ယောက်က robot ရဲ့ လက်ထဲက ball ကို လွတ်ကျအောင်လုပ်လိုက်မယ်ဆိုရင်ဘာဖြစ်မလဲ?

ဒါဆို ဒုတိယ fallback node ဖြစ်တဲ့ fallback noode ကို ပြန် run မှာဖြစ်ပါတယ်။ ဒါသည် reactivity ပဲ။

နောက်အားသာချက်အနေနဲ့ modularity ပေါ့။ subtree တစ်ခုစီဟာ modularity ဖြစ်ပါတယ်။ ဘယ်အပိုင်းကဆို တာ စဥ်းစားနေစရာမလိုပါဘူး။. Subtree တွေကို လွတ်လွတ်လပ်လပ် ပြန်အသုံးချနိုင်ပါတယ်။ ဥပမာ ဘောလုံးကို grasp လုပ်ရမည့် case မျိုးတွေပေါ့။

ဒီလိုအားသာချက်တွေကြောင့် ရှုပ်ထွေးတဲ့ စနစ်တွေမှာ behavior tree ကို သုံးကြတာဖြစ်ပြီး ဥပမာအားဖြင့် robotics နဲ့ game engines လိုကောင်မျိုး တွေအတွက်သုံးကြတာပေါ့။

ကိုစူးစမ်း

10 May 2023

Behavior Tree Code

ကဲ အောက်က tree အတိုင်း code ရေးကြည့်ရအောင်။ BT အတွက် library နဲ့ xml ဖိုင်တစ်ခုလိုပါတယ်။

ကြည့်ရတာတော့ root node က sequence node, child node ဖြစ်တဲ့ check battery က condition node ကျန်တဲ့ ၃ခုကတော့ action node ပေါ့။ ကဲ လိုတာလေးတွေ install ရအောင်။

git clone [e-mail]:BehaviorTree/BehaviorTree.CPP.git

$ cd BehaviorTree.CPP && mkdir build && cd build && cmake .. && make && sudo make install

ဒါဆို compile လုပ်ပြီး စက်ထဲလဲ install လဲလုပ်ပြီးပါပြီ။

ROS2 သမားတွေကတော့ cmake နဲ့ compile မလုပ်ပဲ colcon နဲ့ပဲ workspace ထဲထည့်ပြီး compile လုပ်ပါ။ နှစ်ကြိမ်မြောက်လောက်မှာ build အောင်မြင်ပါလိမ့်မယ်။