SINGLE-AGENT PARALLEL WINDOW SEARCH

We apply parallel window search to single-agent problems by having different processes simultaneously perform iterations of Iterative-Deepening -A* (IDA*) on the same problem but with different cost thresholds. This approach is limited by the time to perform the goal iteration. To overcome this disadvantage, we then consider node ordering. We discuss how global node ordering by minimum h among nodes with equal f = g + h values can reduce the time complexity of serial IDA* by reducing the time of the goal iteration. This approach is limited by the time to perform the iterations prior to the goal iteration. Finally, we combine the two ideas of parallel window search and node ordering to eliminate the weaknesses of each approach while retaining the strengths. The resulting approach, which we call simply parallel window search, can be used to find a near-optimal solution quickly, improve the solution until it is optimal, and then finally guarantee optimality, depending on the amount of time available.