Main Article Content

Abstract

Many applications, ranging from video games to dynamic robotics, require solving single-agent, deterministic search problems in partially known environments under very tight time constraints. Real-Time Heuristic Search (RTHS) algorithms are specifically designed for those applications. As a subroutine, most of them invoke a standard, but bounded, a search algorithm that searches for the goal. In this paper, we present FRIT, a simple approach for single-agent deterministic search problems under tight constraints and partially known environments that unlike traditional RTHS does not search for the goal but rather searches for a path that connects the current state with a so-called ideal tree T . When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and then carries out a reconnection search whose objective is to find a path between the current state and any node in T . The reconnection search is done using an algorithm that is passed as a parameter to FRIT. If such a parameter is an RTHS algorithm, then the resulting algorithm can be an RTHS algorithm. We show, in addition, that FRIT may be fed with a (bounded) complete blind-search algorithm. We evaluate our approach over grid pathfinding benchmarks including game maps and mazes. Our results show that FRIT, used with RTAA*, a standard RTHS algorithm, outperforms RTAA* significantly; by one order of magnitude under tight time constraints. In addition, FRIT(daRTAA*) substantially outperforms daRTAA*, a state-of-the-art RTHS algorithm, usually obtaining solutions 50% cheaper on average when performing the same search effort. Finally, FRIT(BFS), i.e., FRIT using breadth-first-search, obtains best-quality solutions when time is limited compared to Adaptive A* and Repeated A*. Finally we show that Bug2, a pathfinding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.

Keywords

Real-Time Search Reconnection Ideal Tree

Article Details

How to Cite
Hern ́andez C. (2022). Reconnection with the Ideal Tree: A New Approach to Real-Time Search. Journal of Engineering Applied Science and Humanities, 7(1), 50–63. https://doi.org/10.53075/Ijmsirq/656853289

References

  1. Bj ̈ornsson, Y., Bulitko, V., & Sturtevant, N. R. (2009). TBA*: Time-bounded A*. InProc.of the 21st Int’l Joint Conf. on Artificial Intelligence (IJCAI), pp. 431–436.
  2. Bond, D. M., Widger, N. A., Ruml, W., & Sun, X. (2010). Real-time search in dynamicworlds. InProc. of the 3rd Symposium on Combinatorial Search (SoCS), Atlanta,Georgia
  3. Bonet, B., & Geffner, H. (2011). Planning under partial observability by classical replan-ning: Theory and experiments. InProc. of the 22nd Int’l Joint Conf. on ArtificialIntelligence (IJCAI), pp. 1936–1941, Barcelona, Spain.
  4. Bulitko, V., & Lee, G. (2006). Learning in real time search: a unifying framework.Journalof Artificial Intelligence Research,25, 119–157.
  5. Bulitko, V., Bj ̈ornsson, Y., Lustrek, M., Schaeffer, J., & Sigmundarson, S. (2007). Dynamiccontrol in path-planning with real-time heuristic search. InProc. of the 17th Int’lConf. on Automated Planning and Scheduling (ICAPS), pp. 49–56.
  6. Bulitko, V., Bj ̈ornsson, Y., Sturtevant, N., & Lawrence, R. (2011).Real-time HeuristicSearch for Game Pathfinding, pp. 1–30. Applied Research in Artificial Intelligence forComputer Games. Springer Verlag.
  7. Hern ́andez, C., & Baier, J. A. (2011). Fast subgoaling for pathfinding via real-time search.InProc. of the 21th Int’l Conf. on Automated Planning and Scheduling (ICAPS),Freiburg, Germany.