Selection Of Subdomains In Hierarchic Path Generation
Thomas A. Sudkamp, Jill E. Courte · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1989
Hierarchic decomposition has been shown to be an effective technique for efficiently generating near optimal paths through a defended area. The objective is to avoid the combinatorial difficulties associated with searching large graphs by confining the search to specific advantageous subregions. Within the subregions, paths are constructed using the A heuristic search algorithm. The decomposition into subdomains introduces local horizon effects to the path generation process. The local horizon problem arises as a consequence of the required connection of paths generated by independent search procedures in contiguous subdomains. Several techniques are introduced to facilitate the inter-region handoff. The effects of subdomain size and handoff technique on path quality and efficiency are analyzed.