CRII: RI: Memory-efficient Representations for Robot Tasks: Lower Bounds and Scalable Algorithms

具有高度丰富的感知系统(如视觉或激光扫描仪)的微型飞行器(MAV)具有执行重要任务的潜力，例如长期搜索和救援任务。然而，由于其有限的计算资源，现有的大多数方法要么使用无记忆的方法，如反应性避障，要么使用内存效率极低的方法来构建和存储准确的几何表示。因此，一个重要的问题是，为了完成任务，机器人必须为其环境创建什么最低限度的表示。一个相关的问题是，表示的内存效率与机器人完成任务的效率之间的基本权衡是什么。对这些问题的理解有可能极大地增加小牛可以执行的任务类型。出于对高效内存算法的需求，该项目正在开发原则性和一般性的技术，以建立机器人执行任务所需的内存资源。具体地说，该项目将研究：(I)建立内存需求下限的技术，以及(Ii)为机器人任务创建内存高效和以任务为中心的表示法的算法。关键的洞察力是利用和扩展流传输算法和通信复杂性理论的思想，通过将机器人的感官输入视为数据流，在流传输问题和机器人感知之间建立联系。这种类比允许应用最初由理论计算机科学界开发的强大技术，用于证明内存需求的下限，并使用流算法文献中的大量内存效率算法。所产生的工具将应用于计算有限的MAV，在搜救环境中执行各种任务，如搜索、探索和导航。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Micro aerial vehicles (MAVs) with highly rich perceptual systems (e.g., vision or laser scanners) have the potential to perform important tasks, such as long-duration search and rescue missions. However, due to their limited computational resources, most existing approaches either use memoryless approaches, such as reactive obstacle avoidance, or highly memory-inefficient approaches that build and store accurate geometric representations. An important question, therefore, is what is the minimal representation a robot must create of its environment in order to achieve its task. A related question is what are the fundamental tradeoffs between how memory-efficient the representation is and how efficiently the robot can accomplish the task. An understanding of these issues has the potential to dramatically increase the type of tasks that MAVs can perform. Motivated by the need for memory-efficient algorithms, this project is developing principled and general techniques for establishing the memory resources required by robots in order to perform their tasks. Specifically, the project will investigate: (i) techniques for establishing lower bounds on memory requirements, and (ii) algorithms for creating memory-efficient and task-centric representations for robot tasks. The key insight is to leverage and extend ideas from the theory of streaming algorithms and communication complexity, establishing a connection between streaming problems and robot perception by viewing a robot's sensory inputs as constituting the data stream. This analogy enables application of powerful techniques, originally developed by the theoretical computer science community, for proving lower bounds on memory requirements and using the vast suite of memory-efficient algorithms from the streaming algorithms literature. The resulting tools will be applied to MAVs with limited computation performing various tasks such as search, exploration, and navigation in search-and-rescue contexts.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.