AF: Small: Strategy Problems for Robots and Sensor Networks

该奖项旨在开发策略，使移动的机器人和传感器网络能够接近最佳地执行任务，或者至少具有竞争力。 本提案中考虑的任务主要涉及勘探、巡逻、警卫和搜索。 典型的任务是，一组机器人应该探索一个未知的结构，由通道连接的房间组成，或者一个移动的警卫应该巡逻一组走廊，这样他就可以在巡逻期间查看每个走廊一次。 涉及传感器的典型问题是将具有有限感测范围的传感器放置在感兴趣区域中，使得任何入侵者只能移动很小的距离而不会被传感器发现。 对于这些问题中的每一个，都需要开发一种策略，需要分析其最坏情况下的性能，并需要将其与未知的最优策略进行比较，以表明所提出的策略接近最优。 在这个项目中开发的一些策略将由一个合作的机器人实验室实施和测试。

This award aims at developing strategies that allow mobile robots and sensor networks to perform their tasks near-optimally, or at least competitively. The tasks considered in this proposal deal mainly with exploration, patroling, guarding and searching. Typical tasks are that a group of robots should explore an unknown structure consisting of rooms which are connected by passages, or that a mobile guard should patrol a set of corridors, so that he can look down each corridor once during his patrol round. A typical problem involving sensors is to place sensors with a limited sensing range in a region of interest in such a way that any intruder can move only a small distance without being discovered by a sensor. For each of these problems, a strategy needs to be developed, its worst-case performance needs to be analyzed, and it needs to be compared with the unknown optimal strategy, to show that the proposed strategy is nearly optimal. Some of the strategies developed in this project will be implemented and tested by a cooperating robotics lab.