A Heuristic Approach to the Multiagent Pursuit and Evasion Problem in Polygonal Enviroments

Sammanfattning: In this paper heursitic algorithms are developed for the pursuit evasion problem in polygonal enviroments. In this problem, continuous trajectories shall be constructed for a group of pursuers, searching for an evader, in such a way that the evader is guaranteed to be seen at some time during the search. Three fundamentaly dierent heuristic methods are considered: tabu search, genetic algorithms and greedy methods. The result is three heuristic algorithms. Two algorithms are readily implemented in ANSI C, yielding solutions of high quality compared to previous work. The report attains and evaluates statistics on runtime of the algorithms. The algorithms are compared considering the quality and e-ciency for a vast amount of randomly generated enviroments. Key-words : Pursuit and Evasion, Heuristic algorithms, tabu search, greedy methods, genetic algorithms.