## 2 BIT* Algorithm Procedure
### Algorithm Steps  
Step 1: The initialization phase of the BIT* algorithm mainly involves constructing the initial explicit search tree \(T=(V,E)\), defining the state sets, and initializing relevant variables. Initially, the vertex set \(V\) of the tree \(T\) only contains the start state \(x_{start}\), and the edge set \(E\) is empty. The unconnected state set \(X_{uncom}\) contains all goal states, indicating that these states are not yet connected to the tree. To guide the search process, the algorithm introduces two priority queues: a vertex priority queue \(Q_{v}\) for sorting vertices to be expanded based on their priority (evaluated by a heuristic function) and an edge priority queue \(Q_{E}\) for sorting edges to be processed based on their priority (also evaluated by a heuristic function). In addition, the algorithm maintains the following variables: the set of solution vertices found so far \(V_{sol^{\prime}n}\) (initially empty), the set of unexplored vertices \(V_{uncappend}\) (initially containing the start vertex), the set of newly sampled points \(X_{new}\) (initialized to the unconnected state set \(X_{uncom}\)), and the cost of the current best solution \(Ci\) (initialized to infinity \(\infty\), indicating that no feasible solution has been found yet). In subsequent iterations, \(C_{i}\) will be updated to the minimum cost of the goal vertices in the currently found solutions. Step 2: The core of the BIT* algorithm is an iterative main loop that continues until a predefined termination condition is met, such as reaching the maximum runtime or finding a path that meets specific quality requirements. In each iteration of the main loop, the algorithm performs the following steps to progressively build and optimize the path:  
1. Sampling: The algorithm first samples a fixed number \(m\) of new state \(X_{\text{sampling}}\) from the informed set. The informed set is defined by the heuristic function and the current best solution cost \(C_{i}\), and it contains the regions of the state space that are likely to yield better paths. By sampling from the informed set, the algorithm can explore promising regions more efficiently and avoid wasting computational resources on areas that are unlikely to produce an optimal solution. 2. Pruning: When both the edge queue \(Q_{E}\) and the vertex queue \(Q_{v}\) are empty, it indicates that the current tree's expansion has no better edges or vertices to choose from for the time being, and the algorithm enters the pruning phase. The pruning operation aims to remove vertices and edges that cannot provide a better solution for the current or future paths, thereby optimizing the tree's structure and reducing the burden of subsequent calculations. These removed elements will be temporarily stored in the reuse set \(X_{\text{reuse}}\) so that they can be reused as needed in subsequent iterations. Specifically, the pruning process traverses all vertices and edges in the current tree and judges whether they have the potential to improve the path based on their cost to the start state, estimated cost to the goal state, and the current best solution cost \(C_{i}\). If a vertex or edge is deemed unable to provide a better solution, it is removed from the tree and added to the \(X_{\text{reuse}}\) set. 3. Update: After completing the pruning operation, the algorithm merges the reuse set \(X_{\text{reuse}}\) with the new sample points \(X_{\text{sampling}}\) to form a new set of sample points \(X_{\text{new}}\). The unconnected state set \(X_{\text{uncom}}\) is updated to include all newly sampled points. Then, the vertex priority queue \(Q_{v}\) is reinitialized to contain all vertices in the current tree in order to select the best vertex for expansion in the subsequent steps. 4. Vertex Expansion and Edge Selection: The algorithm decides whether to perform vertex expansion or edge selection based on the head elements of \(Q_{v}\) and \(Q_{E}\).