# Learning and Planning Based on Merged Experience from Multiple Situations for a Service Robot
## 2 Learning and Planning Methods
### Planning Based on Activity Schema with Merging Optimization and Partially Backtracking Techniques  
#### 2.4.1 Planning Based on Activity Schema with Merging Optimization  
To find an optimal solution to a task planning problem \(P\) in a given domain \(D\), we developed a schema-based optimized planner (SBOP) which is based on the learned activity schema, and actions merging optimization and partially backtracking techniques are adopted. The SBOP is presented in Algorithm 2. SBOP begins via selecting an activity schema \(ma\) with respect to a given task \(t\). After instantiation, a global task tree rooted as '_tastree_' is created to store the task tree, and a global plan tree rooted as '_plantree_' is created to store the action chains that implement the task goal [19]. Given that the execution of the lowest-level actions changes the state of the world and affects the judgment of its subsequent nodes' preconditions, the check state of the current node depends on the check state of its children nodes. The search algorithm is designed as a depth-first algorithm. Only when all the children nodes are checked, is the next node in the same branch checked. When all the nodes in the current branch are checked, the parent node is returned to check the next node of the parent node. We set three values for the check state of an abstract method instance node: \"0\" indicates that the nodes in its branch have not been checked, \"1\" indicates that all the nodes in one of its branches have been detected, \"2\" indicates that it is being checked. The abstract method \(am\) is checked layer by layer according to the structure of the selected activity schema. In this process, the current world states are substituted into the preconditions of each branch in \(am\) to check whether \(sub_{i}\) is applicable in a state \(S\) (\(sub_{i}\) is applicable in a state \(S\) only if there is a binding \(\theta\) that binds all variables in the corresponding task's arguments [12], referring to line 19). If there is such a branch, the subtasks \(sub_{i}\theta\) of _activenode_ are added to _tasktree_. Then, the check state of _activenode_ is set to \"2\", and the nodes in the \(sub_{i}\theta\) are checked one by one (lines 21-22). If such a branch does not exist, the preconditions that are not satisfied will be published. If _activenode_ is an instance of an abstract operator, then \(S\) is updated to \(S\)' by applying active action to the transition function. If \(S\)' is true, the current action \(a\) is added to _plantree_ and _tasktree_ (line 30). The condition for terminating a loop in this check is that a branch of the current activity schema is traversed, that is, state(\(ma\)) = 1. It is very likely that the task contains multiple subtasks that conform to the same schema. It is necessary to determine whether the search should be terminated by judging the satisfactory conditions in the goal proposition in \(S^{\prime}\). Finally, the planner stops and returns the _tasktree_ and _plantree_. To improve the execution efficiency, the whole plan is subject to merging optimization, and the action cliques [19] are generated by selecting the actions layer by layer of the plan tree in a top-down manner until the final plan is obtained (line 34). The optimization is modelled as a MWCP (maximum-weight clique problem) [24] based on the graph theory. Finally, the optimized plan is taken as the output. ```
1:\(\{t,AM,\Omega\}\leftarrow\) select an activity schema



The failed action in a _tasktree_ can be obtained by Action2 Task(), which maps the actions from the _planttree_ to _tasktree_ according to a dictionary (line 2). Replanning is conducted for the task tree under the parent node _failedParent_ of the failed action. We first translate _failedParent_ to the corresponding abstract method _am_ in the activity schema, and check whether the branch _presubi_ in _am_ exists that is applicable in state \(S\) (lines 5-6). If no such branch is identified, we will check whether there exists _amf_! in _AMF_ applicable in state \(S\).