The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

MSc Thesis #9723

Title:Methods for Solving the Search and Rescue Problem Using Genetic Algorithms
Authors:Farquhar,JD
Date:Sep 1997
Presented:
Keywords:
Abstract:Planning efficient search operations is an important requirement in many fields including the police, mountain rescue and coast-guard. Use of Information Technology is only slowly beginning to find its way into this domain with rudimentary systems to predict the lcoation of lost individuals based on statistical analysis of previous similar searches now being used [Booth95]. However even with such systems the actual routing of searchers over the region to search is left to a human coordinator relying solely on their experience to produce efficient searches. However when planning such searches speed is of the utmost importance with delays potentially costing peoples lives. Hence a reliable, flexible method for quickly producing high quality search plans to aid the human coordinator are potentially extremely beneficial. This thesis discusses the development of such a computerised planner which sohould be able to provide a near optimal search plan in little time given a terrain map, the probable locations of the target and the number and types of searcher available. Initially a planner based on hill climbing was developed but the solutions generated were of unreliable quality as the planner easily got caught in local optima. Because of this a Genetic Algorithm (GA) based planner was developed and found to give good, reliable performance when problem specific operators are used. The performance of the GA was further improved by adding heuristic information in the mutation and initialisation operations giving about one third reduction in run time for superior results. The Genetic Algorithm can consistently and rapidly provide high quality plans for simple test problems and as such could form the basis of a planner for use in actual searches.
Download:NO ONLINE COPY

[Search These Pages] [DAI Home Page] [Comment]