论文标题
使用多级图形搜索的热量滑翔机的多代理计划
Multi-agent Planning for thermalling gliders using multi level graph-search
论文作者
论文摘要
本文解决了一组滑翔机的路径计划问题。滑翔机的任务是访问一组兴趣点。滑翔机的范围有限，但能够通过访问称为Thermals的特殊点来增加其范围。本文解决的问题是对滑翔机的路径计划，以至于最大化滑翔机访问的利息点总数。这被称为多代理问题。首先将其分解为几个单一代理问题来解决问题。在单一代理问题中，一组兴趣点分配给单个滑翔机。通过规划一条路径来解决此问题，该路径最大化分配的集合中访问的兴趣点的数量。如我们先前的工作所示，这是通过统一的成本图搜索来实现的。现在，多代理问题包括确定每个滑翔机的最佳分配（感兴趣的点）。提出了解决此问题的两种方法，即早期工作中所示的蛮力搜索方法和Branch \＆Bound类型的图形搜索。分支和约束方法是本文的主要贡献。事实证明，这种方法是最佳的，并且证明使用模拟比蛮力搜索更快。
This paper solves a path planning problem for a group of gliders. The gliders are tasked with visiting a set of interest points. The gliders have limited range but are able to increase their range by visiting special points called thermals. The problem addressed in this paper is of path planning for the gliders such that, the total number of interest points visited by the gliders is maximized. This is referred to as the multi-agent problem. The problem is solved by first decomposing it into several single-agent problems. In a single-agent problem a set of interest points are allocated to a single glider. This problem is solved by planning a path which maximizes the number of visited interest points from the allocated set. This is achieved through a uniform cost graph search, as shown in our earlier work. The multi-agent problem now consists of determining the best allocation (of interest points) for each glider. Two ways are presented of solving this problem, a brute force search approach as shown in earlier work and a Branch\&Bound type graph search. The Branch&Bound approach is the main contribution of the paper. This approach is proven to be optimal and shown to be faster than the brute force search using simulations.
