| Autor: | Jeffery L. Kennington, K. R. Lewis, Richard V. Helgason |
|---|---|
| Rok vydání: | 2001 |
| Předmět: |
Mathematical optimization
Control and Optimization Computer Networks and Communications Computer science Path generation Management Science and Operations Research Any-angle path planning Computer Science::Robotics Cruise missile Line segment Artificial Intelligence Search algorithm Simple (abstract algebra) Path (graph theory) Software Information Systems |
| Zdroj: | Journal of Heuristics. 7:473-494 |
| ISSN: | 1381-1231 |
| Popis: | This manuscript presents a heuristic algorithm based on geometric concepts for the problem of finding a path composed of line segments from a given origin to a given destination in the presence of polygonal obstacles. The basic idea involves constructing circumscribing triangles around the obstacles to be avoided. Our heuristic algorithm considers paths composed primarily of line segments corresponding to partial edges of these circumscribing triangles, and uses a simple branch-and-bound procedure to find a relatively short path of this type. This work was motivated by the military planning problem of developing mission plans for cruise missiles, but is applicable to any two-dimensional path-planning problem involving obstacles. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink