Extending discrete search to hybrid system search introduces two new decisions in optimization: action discretization and action timing discretization. For this problem we address the latter decision: How could a search algorithm choose when to branch the search tree and consider possible actions? We thus use a predefined 8-direction, 3-speed (full, half, stop) discretization. From the perspective of the search algorithm, action discretizations are static, i.e. the search algorithm cannot affect the action discretization. However, from the perspective of the search algorithm, action timing discretizations are dynamic, i.e. branching points are chosen by the search algorithm. For this reason, we call such searches ``SADAT searches'' as they have Static Action and Dynamic Action Timing discretization.
In Chapter 5 of Neller's Dissertation, we introduce a novel variation of Best-First Search (BFS) which allows limited flexibility in varying action timing. In our variation of BFS, we (1) assume a given largest time-step between actions, and (2) redefine node expansion to allow new open nodes along existing branches. Regarding (1), we take as a parameter Delta t, a real-valued number of time units, which serves as a default delay time between an expanded node and its new leaf children. Regarding (2), we redefine node expansion for three cases: the root node case, leaf node case, and internal node case. These cases correspond respectively to a node having no parent and no children, having a parent and no children, and having a parent and a child. One can prove inductively that these are the only three cases which can occur for our method of expansion.
The algorithm begins as normal BFS with the root node in the open heap. With each iteration, the node with the lowest f'(node) is extracted from the heap. If the node is a goal node, the algorithm terminates with success. Otherwise, its children are generated and placed on the open heap. The key difference is how new nodes are generated.
For a root node, we simply generate its children. Each child is computed by cloning its parent, making the associated legal move, and simulating forward Delta t. The child is then placed in a heap according to f'(child).
For a leaf node, there is a slight difference. In addition to generating its children, we also generate a new parent node halfway (with respect to time delay) between the leaf node and its current parent node.
For an internal node, there is yet another difference. In addition to generating new children, i.e. all children but its single existing child, and a new parent (as with the leaf node), it generates a new child halfway between itself and its pre-existing child.
The important thing to note about this algorithm is that it allows a more refined temporal search than best-first search with a fixed delay. This is both a strength and a weakness under different circumstances. While it can sometimes better approximate optimal solutions or find solutions which cannot be found without such refinement, one can easily generate pathological cases where SADAT Simple Best-First Search cannot find solutions which can be found using best-first search with a fixed delay.
For the full algorithm and further details, see the reference below.