Parallel algorithms for visibility analysis and path planning

In search and rescue (SAR) and emergency planning operations real-time response is critical, particularly when lives are endangered. Until recently, such operations were planned manually by experts in the field using tools such as templates, protractors and calculators. An initiative from the Department of National Defence of Canada has recommended the development of a prototype computerized tool to help the experts in the planning phase of these operations.;This thesis, which was carried out under PRECARN project Passport, addresses two types of algorithms that are at the core of SAR and emergency planning operations: airborne path planning for surveillance and search, and land path planning for mobility analysis and rescue route determination.;The major limitation associated with these algorithms is the high computational cost incurred from the treatment of vast amounts of data representing elevation, transportation networks, vegetation and other soil characteristics. In addition, the programming complexity of these algorithms is not negligible. These issues demand the high performance computing capabilities and relative ease of programming of today's multiprocessor shared-memory computers, as well as algorithms that are scalable and highly efficient.;Parallel algorithms for visibility analysis and path planning using digital terrain data are proposed. The algorithms have been implemented on a Sun symmetric multiprocessor (SMP) SPARC 20 machine and integrated with the Passport airborne path planning and land path planning software. Results of experiments are presented. Some results are compared with a previous implementation on the MasPar MP-1 and MP-2 massively parallel computers.