RI: Small: Any-Angle Search

在本项目中，PI研究了任意角度的搜索方法。任意角度搜索方法是启发式搜索方法A*的变体，通过仅沿网格边缘传播信息(以实现较小的运行时间)，而不将路径限制到网格边缘(以查找短的“任意角度”路径，即其标题可按任意角度改变的路径)，从而使搜索与路径优化交错。该项目的目标是将任何角度的搜索从几种孤立的搜索方法扩大到一个广为人知的框架，并扩大其适用性。为此，PI正在开发新的任意角度搜索方法并分析它们的性质，这是因为即使是基本性质通常也不会从A*转移到它们。该团队还将评估所有新的和现有的任意角度搜索方法之间以及与其他搜索方法的比较，例如，了解它们如何在运行时间、路径长度和内存消耗之间进行权衡。任意角度搜索是最近的一种搜索范例，有望为包括水下和空中机器人在内的移动机器人带来一类新的强大的路径规划方法。该项目包括传播活动，以提高人们对人工智能和机器人技术中任何角度搜索的认识(例如通过教程、开放源代码和网络小应用程序)，并为研究生和本科生提供研究机会。

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.