Evaluation of real-time search algorithms in dynamic worlds (summary of results)

Author

Shekhar, Shashi ; Hamidzadeh, Babak

Author_Institution

Dept. of Comput. Sci., Minnesota Univ., Minneapolis, MN, USA

fYear

1992

fDate

10-13 Nov 1992

Firstpage

6

Lastpage

13

Abstract

A classification of different dynamic worlds is presented. A detailed model of a dynamic world where changes occur in edge costs around a zero mean is provided. A formal analysis of the model suggests that the static rank ordering of solution paths is preserved in the model. Two real-time search algorithms, DYNORAII and RTA*, for the real-time path planning problem are analyzed. Results on the path planning problem using the proposed dynamic model of graphs are given. The ability of DYNORAII and RTA* to minimize response times in dynamic environments has been evaluated experimentally. It is found that DYNORAII outperforms RTA* in minimizing response times

Keywords

path planning; real-time systems; search problems; DYNORAII; RTA*; dynamic environments; dynamic worlds; edge costs; formal analysis; path planning problem; real-time search algorithms; static rank ordering; zero mean; Algorithm design and analysis; Application software; Artificial intelligence; Computer science; Costs; Heuristic algorithms; Path planning; Predictive models; Problem-solving; Uncertainty;

fLanguage

English

Publisher

ieee

Conference_Titel

Tools with Artificial Intelligence, 1992. TAI '92, Proceedings., Fourth International Conference on

Conference_Location

Arlington, VA

Print_ISBN

0-8186-2905-3

Type

conf

DOI

10.1109/TAI.1992.246379

Filename

246379