Abstract
In this paper we propose a real-time search algorithm called Real-Time Target Evaluation Search (RTTES) for the problem of searching a route in grid worlds from a starting point to a static or dynamic target point in real-time. The algorithm makes use of a new effective heuristic method which utilizes environmental information to successfully find solution paths to the target in dynamic and partially observable environments. The method requires analysis of nearby obstacles to determine closed directions and estimate the goal relevance of open directions in order to identify the most beneficial move. We compared RTTES with other competing real-time search algorithms and observed a significant improvement on solution quality.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Russell S, Norving P (1995) Artificial intelligence: A modern approach. Prentice Hall, Inc.
Gutmann J, Fukuchi M, Fujita M (2005) Real-time path planning for humanoid robot navigation. International joint conferance on artificial intelligence IJCAI-05, pp 1232–1237
Knight K (1993) Are many reactive agents better than a few deliberative ones? In: Proceedings of the 10th int’l joint conf. on artificial intelligence, pp 432–437
Korf R (1990) Real-time heuristic search. Artif Intell 42(2–3):189–211
Ishida T, Korf R (1995) Moving target search: a real-time search for changing goals. IEEE Trans Patt Anal Mach Intell 17(6):97–109
Ishida T (1996) Real-time bidirectional search: coordinated problem solving in uncertain situations. IEEE Trans Patt Anal Mach Intell 18(6)
Undeger C (2001) Real-time mission planning for virtual human agents. M.Sc. Thesis in Computer Engineering Department of Middle East Technical University, 2001
Stentz A (1994) Optimal and efficient path planning for partially-known environments. In: Proceedings of the IEEE international conference on robotics and automation
Mudgal A, Tovey C, Greenberg S, Koenig S (2005) Bounds on the travel cost of a mars rover prototype search heuristic. SIAM J Discrete Math 19(2):431–447
Stentz A (1995) The focussed D* algorithm for real-time replanning. In: Proceedings of the int’l joint conference on artificial intelligence
Koenig S, Likhachev M (2002) D* lite. In: Proceedings of the national conference on artificial intelligence, pp 476–483
Koenig S, Likhachev M (2002) Improved fast replanning for robot navigation in unknown terrain. In: Proceedings of the international conference on robotics and automation
Koenig S, Likhachev M (2005) Fast replanning for navigation in unknown terrain. IEEE Trans Robo 21(3):354–363
Koenig S (2004) A comparison of fast search methods for real-time situated agents. AAMAS 2004 pp 864–871
Undeger C, Polat F, Ipekkan Z (2001) Real-time edge follow: A new paradigm to real-time path search. In: The proceedings of GAME-ON
Undeger C, Polat F (2007) Real-time edge follow: a real-time path search approach. IEEE Transaction on Systems, Man and Cybernetics,Part C.
Undeger C, Polat F (2006) Real-time target evaluation search. In: 5th int’l joint conf on autonomous agents and multiagent systems, pp 332–334
Tanenbaum A (1996) Computer networks. Prentice-Hall, Inc.
Koenig S, Likhachev M, Liu Y, Furcy D (2004) Incremental heuristic search in artificial intelligence. Artif Intell Magazine
Konar A (2000) Artificial intelligence and soft computing: behavioral and cognitive modeling of human brain. CRC Press LLC
Michalewicz Z (1986), Genetic algorithms + data structure − evolution programs. Springer-Verlag, New York
Sugihara K, Smith J (1997) Genetic algorithms for adaptive planning of path and trajectory of a mobile robot in 2d terrains. Technical Report, number ICS-TR-97-04, University of Hawaii, Department of Information and Computer Sciences
Cheng P, LaValle SM (2002) Resolution complete rapidly-exploring random trees. In: Proceedings of IEEE int’l conf on robotics and automation, pp 267–272
LaValle S, Kuffner J (1999) Randomized kinodynamic planning. In: Proceedings of the IEEE international conference on robotics and automation (ICRA’99)
LaValle SM, Kuffner JJ (2001) Rapidly-exploring random trees: progress and prospects, ser. Algorithmic and Computational Robotics: New Directions. A K Peters, Wellesley, MA, pp 293–308
Kavraki L, Latombe J (1998) Probabilistic roadmaps for robot path planning, ser. In Practical Motion Planning in Robotics: Current and Future Directions. Addison-Wesley
Sanchez G, Ramos F, Frausto J (1999), Locally-optimal path planning by using probabilistic roadmaps and simulated annealing. In: Proceedings IASTED robotics and applications international conference
Hernndez C, Meseguer P (2005) Lrta*(k). Int’l joint conf on artificial intelligence IJCAI-05, pp 1238–1243
Shimbo M, Ishida T (2003) Controlling the learning process of real-time heuristic search. Artif Intell 146(1):1–41
LVJ, Skewis T (1987) Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algoritmica 2:403–430
Kamon I, Rivlin E, Rimon E (1996) A new range-sensor based globally convergent navigation algorithm for mobile robots. In: Proc of the IEEE int’l conf on robotics and automation vol. 1, pp 429–435
Bruce J, Veloso M (2002) Real-time randomized path planning for robot navigation. In: Proceedings of int’l conf on intelligent robots and systems, pp 2383–2388
Hsu D, Kindel R, Latombe J, Rock S (2002) Randomized kinodynamic motion planning with moving obstacles. Int J Robotics Res 21(3):233–255
Stilman M, Kuffner J (2005) Navigation among movable obstacles: Real-time reasoning in complex environments. Int J Humanoid Robo 2(4):1–24
Koenig S, Likhachev M (2006) Real-time adaptive a*. In: 5th int’l joint conference on autonomous agents and multiagent systems, pp 281–288
Hamidzadeh B, Shekhar S (2005) Dynoraii: A real-time path planning algorithm. Int J Artif Intell Tools 2(1):93–115
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Undeger, C., Polat, F. RTTES: Real-time search in dynamic environments. Appl Intell 27, 113–129 (2007). https://doi.org/10.1007/s10489-006-0023-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10489-006-0023-1