OCBP – “Introducing Darmok” part4
On-Line Plan Expansion and Execution
During execution, the plan expansion, plan execution and plan adaptation occur in parallel in order to maintain a current partial plan tree that the system is executing. A partial plan tree (or simply the “plan”) is represented as a tree consisting of two types of nodes: goals and snippets.
Initially, the plan consists of a single goal corresponding to the planning task at hand. In particular, in Darmok the initial goal is always “win the game”. Then, the plan expansion module asks the plan retrieval module to retrieve a snippet for that goal. That snippet might have several subgoals, for which the plan expansion module will again ask the plan retrieval module to retrieve snippets, and so on. For instance, at the top of Figure 8 we can see a sample plan, where the top goal is to “win”. The snippet assigned to the “win” goal has three subgoals, namely “build base”, “build army” and “attack”.
Figure 9 shows the algorithm the plan expansion module executes at every execution cycle given a plan p and a game state S. The plan expansion module is constantly querying the current plan to see if there is a ready open goal. When this happens, the open goal is sent to the plan retrieval module to retrieve a snippet for it. Then, that snippet is sent to the plan adaptation module, and then inserted in the current plan, marked as pending.
Function PlanExpansion(p, S)
G = GetReadyOpenGoals(p)
For g ∈ G Do
pg = RetrievePlan(g, S)
pg = AdaptPlan(pg , g, S)
p = InsertSnippetInPlan(p, g, pg )
EndFor
Return p
EndFunction
Figure 9: Plan expansion algorithm used in Darmok, where p is the current plan
Function PlanExecution(p, S)
p = startReadySnippets(p,S)
p = sendActionsToExecution(p,S)
p = updateSnippetStatus(p,S)
p = updateActionStatus(p,S)
Return p
EndFunction
Figure 10: Plan execution algorithm used in Darmok, where p is the current plan and S is the current game state.
Figure 10 shows the algorithm that the plan execution module executes at each execution cycle, composed of four steps:
• startReadySnippets: For each pending snippet, the execution module evaluates the preconditions, and as soon as they are met, the snippet starts its execution. If the current game state has changed since the time the and S is the current game state. plan retrieval module retrieved it, the snippet is handed back to the plan adaptation module to make sure that the plan is adequate for the current game state.
• sendActionsToExecution: If any of the executing snippets have any basic actions, and those actions have all its preconditions satisfied, then they are sent to Wargus to be executed. If the preconditions of the actions are not satisfied, the snippet is sent back to the plan adaptation module to see if the plan can be repaired. If after a certain amount of time t1 (set to 2000 game cycles in our experiments) it cannot, then the snippet is marked as failed, and thus its corresponding goal is open again (thus, the system will have to find another plan for that goal).
• updateSnippetStatus: The execution module periodically evaluates the alive conditions and success conditions of each snippet. If the alive conditions of an executing snippet are not satisfied, the snippet is marked as failed, and its goal is open again. If the success conditions of a snippet are satisfied, the snippet is marked as succeeded.
• updateActionStatus: Whenever a basic action succeeds or fails, the execution module updates the status of the snippet that contained it. When a basic action succeeds, the executing snippet can continue to the next step. When a basic action fails, the snippet is marked as failed, and thus its corresponding goal is open again.
