Online Detection of Dead States in Real-Time Agent-Centered Search
作者： Nathan R. Sturtevant , Ariel Felner , Guni Sharon
DOI:
关键词: Algorithm 、 Pruning (decision trees) 、 Speedup 、 State (computer science) 、 A priori and a posteriori 、 Mathematics
摘要: In this paper we introduce techniques for state pruning atruntime in a priori unknown domains. We describe how toidentify states that can be deleted from the state-space whenlooking both optimal and suboptimal solutions. discussgeneral graphs special cases like 8-connected grids.Experimental results show speed up of to an order ofmagnitude when applying our on real-time agentcenteredsearch problems.
参考文章(24)
Nathan R. Sturtevant, Yngvi Björnsson, Vadim Bulitko, On learning in agent-centered search adaptive agents and multi-agents systems. pp. 333- 340 ,(2010) , 10.5555/1838206.1838253
Yngvi Björnsson, Kári Halldórsson, Improved heuristics for optimal pathfinding on game maps national conference on artificial intelligence. pp. 9- 14 ,(2006)
Daniel Harabor, Alban Grastien, Online graph pruning for pathfinding on grid maps national conference on artificial intelligence. pp. 1114- 1119 ,(2011)
Nathan R. Sturtevant, Memory-efficient abstractions for pathfinding national conference on artificial intelligence. pp. 31- 36 ,(2007)
Nir Pochter, Jeffrey S. Rosenschein, Aviv Zohar, Exploiting problem symmetries in state-based planners national conference on artificial intelligence. pp. 1004- 1009 ,(2011)
Asaf Shiloni, Gal A. Kaminka, Noa Agmon, Of robot ants and elephants adaptive agents and multi agents systems. pp. 81- 88 ,(2009)
Nir Pochter, Jeffrey S. Rosenschein, Ariel Felner, Aviv Zohar, Search space reduction using swamp hierarchies national conference on artificial intelligence. pp. 155- 160 ,(2010)
Sebastian Thrun, Learning Occupancy Grid Maps with Forward Sensor Models Autonomous Robots. ,vol. 15, pp. 111- 127 ,(2003) , 10.1023/A:1025584807625
László Mérõ, A heuristic search algorithm with modifiable estimate Artificial Intelligence. ,vol. 23, pp. 13- 27 ,(1984) , 10.1016/0004-3702(84)90003-1
Richard E. Korf, Real-time heuristic search Artificial Intelligence. ,vol. 42, pp. 189- 211 ,(1990) , 10.1016/0004-3702(90)90054-4