In this project, the PI studies any-angle search methods. Any-angle search methods are variants of the heuristic search method A* that interleave the search with path optimizations by propagating information only along grid edges (to achieve small runtimes) but without constraining the paths to grid edges (to find short "any-angle" paths, namely paths whose headings can change by any angle). The objective of this project is to broaden any-angle search from a few isolated search methods to a well-understood framework and to extend its applicability. To this end, the PI is developing new any-angle search methods and analyzing their properties, which is complicated by the fact that even base properties often do not transfer from A* to them. The team will also evaluate all new and existing any-angle search methods against each other and against alternative search methods, for example, to understand how they trade off among runtime, path length and memory consumption.
Any-angle search is a recent search paradigm that promises to result in a new class of powerful path-planning methods for mobile robots, including underwater and aerial vehicles. The project includes dissemination activities to raise awareness of any-angle search in artificial intelligence and robotics (such as via tutorials, open-source code and web applets) and offers research opportunities to both graduate and undergraduate students.
