Behavior Tree Learning for Robotic Task Planning through Monte Carlo DAG Search over a Formal Grammar

We present an algorithm for learning behavior trees for robotic task planning, which alleviates the need for time-intensive or infeasible manual design of control architectures. Our method involves representing the search space of behavior trees as a formal grammar and searching over this grammar by means of a new generalization of Monte Carlo tree search (MCTS) for directed acyclic graphs (DAGs), named MCDAGS. Additionally, our method employs simulated annealing to expedite the aggregation of the most functional subtrees. We present simulated experiments for a marine target search and response scenario, and an abstract task selection problem. Our results demonstrate that the learned behavior trees compare favorably with a manually-designed tree, and outperform baseline learning methods. Overall, these results show that our method is a viable technique for the automatic design of behavior trees for robotic task planning.