RI: Small: Any-Angle Search

RI：小：任意角度搜索

• 批准号: 1319966
• 负责人: Sven Koenig
• 金额: $ 43.7万
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319966&HistoricalAwards=false
• 关键词: RI; Small; Any; Angle; Search

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.

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