## 5 Planning Algorithm  
This paper aims to search for high-quality plans within a partially observable environment. Therefore, it necessitates the integration of partial observability with optimization procedures. More specifically, the obtained plan is capable of not only addressing the previously analyzed aspects of partial observability but also achieving high quality based on the evaluation of certain objectives. In this section, we elaborate on the planning algorithm that integrates the heuristic with probabilistic contingent planning. The planner takes the planning problem \(P=(bs_{0},\omega_{0},D)\) as the input, which includes the initial belief state \(bs_{0}\), the initial task network \(\omega_{0}\), and the planning domain \(D\). The initial belief state encapsulates the initial information about the partially observable environment. Finally, the planning algorithm aims to generate a plan for \(P\). The planning procedure is shown as Algorithm 2. At the beginning of the algorithm, the plan \(\pi\) is assigned by an empty set. The framework of the algorithm can be regarded as a loop that plans each step and moves forward recursively. When the plan is generated successfully or the algorithm returns failure, the whole cyclic procedure stops and the planning ends. Each step involves executing the tasks in the task network and proceeding with the next iteration of the process. The planning forward step is recursive, meaning that it calls the next iteration of the algorithm, which starts again with the next task in the sequence. This cyclical process continues until all tasks in the network have been successfully planned and executed, ensuring that the overall objective is achieved in the most efficient manner possible. HTN planning involves breaking down complex tasks into simpler, more manageable subtasks. The planning forward step is elaborated as follows. The tasks in the task network are defined by three categories: compound tasks, actuation primitive tasks, and sensing primitive tasks, corresponding to methods, actuation operators, and sensing operators. Hence, the algorithm proceeds in three ways. From line 4 to line 16, when the current task is an actuation primitive task, an actuation operator is instantiated into a set of actions at the belief state \(bs\) that satisfies the preconditions of the actions. The action that has minimal cost is selected. The belief state and the task network are updated, respectively, and plan \(\pi\) is appended with \(a\). Line 17 to line 27 describes the situation where the current task is a compound task. _Active_ is a set that consists of the instances of the available methods. If _Active_ is not null, the instance that minimizes the cost is chosen. All the tasks in the task network will be updated from the bottom up at line 21. The detailed procedure for updating will be discussed in Algorithm 3. If the task network is checked to be not consistent by Algorithm 3, updating will be suspended, and backtracking happens to search for other available instances of the methods. Otherwise, the task network will be renewed at line 23 and the planning will proceed. When the current task is a sensing primitive task, the planner senses the whole belief state for uncertainty and calls the HQCP recursively, which forms a conditional plan. From line 28 to line 36, when the current task is a sensing primitive task, the algorithm sensesevery ground state in the belief state, adding the sensing action and the observation into the corresponding subplan. Backtracking and planning forward are mutually exclusive. When the planner cannot find a valid method to decompose a task or there are no available actions to accomplish a primitive task, or the cost of the current task network is not minimum, the algorithm will not proceed with planning forward. Instead, the planner will backtrack, which involves a series of corrective actions: removing the actions that have been planned so far, reverting the belief states to a prior state, and restoring the task network.