A security robot decides what to do with a behaviour tree. Ten times a second the tree is ticked from its root, and every node it visits answers with a status: "SUCCESS", "FAILURE" or "RUNNING" (still busy). The tree is given as nested tuples:
("action", name): a leaf that does something. Ticking it returns that action's status for this tick.("cond", name): a leaf that checks something. Its status for this tick is"SUCCESS"or"FAILURE".("seq", child1, child2, ...): a Sequence. Tick the children from the first; as soon as one returns"FAILURE"or"RUNNING", stop and return that status. If every child succeeds (or there are none), return"SUCCESS".("fallback", child1, child2, ...): a Fallback. Tick the children from the first; as soon as one returns"SUCCESS"or"RUNNING", stop and return that status. If every child fails (or there are none), return"FAILURE".("not", child): tick the child and swap"SUCCESS"and"FAILURE";"RUNNING"stays"RUNNING".
Ticks have no memory: every tick starts again at the root and at the first child of every Sequence and Fallback, so a newly true condition can interrupt an action that was running. ticks is a list with one dict per tick, giving the status of every leaf name for that tick (a name may appear in several leaves).
Write tick_tree(tree, ticks) that returns one pair per tick: (root status, actions), where actions lists the names of the action leaves that were ticked, in the order they were ticked.
Examples
Input: tree = ("fallback",
("seq", ("cond", "battery_low"), ("action", "go_dock")),
("seq", ("cond", "person_seen"), ("action", "greet")),
("action", "patrol"))
ticks = [{"battery_low": "FAILURE", "person_seen": "FAILURE", "go_dock": "RUNNING", "greet": "RUNNING", "patrol": "RUNNING"},
{"battery_low": "FAILURE", "person_seen": "SUCCESS", "go_dock": "RUNNING", "greet": "RUNNING", "patrol": "RUNNING"},
{"battery_low": "SUCCESS", "person_seen": "SUCCESS", "go_dock": "RUNNING", "greet": "RUNNING", "patrol": "RUNNING"},
{"battery_low": "SUCCESS", "person_seen": "FAILURE", "go_dock": "FAILURE", "greet": "SUCCESS", "patrol": "SUCCESS"}]
Output: [("RUNNING", ["patrol"]), ("RUNNING", ["greet"]), ("RUNNING", ["go_dock"]), ("SUCCESS", ["go_dock", "patrol"])]
Explanation: the robot patrols, then greets a visitor, then a low battery interrupts the
greeting. In the last tick docking fails, the visitor is gone, and patrolling succeeds.
Input: tree = ("seq", ("not", ("cond", "door_closed")), ("action", "drive_through"), ("action", "beep"))
ticks = [{"door_closed": "SUCCESS", "drive_through": "SUCCESS", "beep": "SUCCESS"},
{"door_closed": "FAILURE", "drive_through": "RUNNING", "beep": "SUCCESS"}]
Output: [("FAILURE", []), ("RUNNING", ["drive_through"])]
Input: tree = ("action", "wait"), ticks = []
Output: []
Goals
- Evaluate a behaviour tree given as nested tuples with a short recursive function
- Apply the Sequence, Fallback and Not rules, with RUNNING passed up the tree
- Record which actions a tick actually reached, in order