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

具有高度丰富感知系统的微型飞行器（MAV）（例如，视觉或激光扫描仪）具有执行重要任务的潜力，例如长时间的搜索和救援任务。 然而，由于其有限的计算资源，大多数现有的方法要么使用无记忆的方法，如反应式避障，或高度记忆效率低下的方法，建立和存储准确的几何表示。 因此，一个重要的问题是，机器人为了完成任务，必须创建的环境的最小表示是什么。 一个相关的问题是，在表示的内存效率和机器人完成任务的效率之间有什么基本的权衡。 对这些问题的理解有可能大大增加MAV可以执行的任务类型。出于对内存高效算法的需求，该项目正在开发用于建立机器人执行任务所需的内存资源的原则性和通用技术。具体来说，该项目将研究：（i）建立内存需求下限的技术，以及（ii）为机器人任务创建内存效率和以任务为中心的表示的算法。关键的洞察力是利用和扩展的想法，从理论的流算法和通信的复杂性，建立一个连接之间的流问题和机器人感知，通过查看机器人的感官输入构成的数据流。 这种类比使得最初由理论计算机科学社区开发的强大技术能够应用于证明内存需求的下限，并使用来自流算法文献的大量内存高效算法。由此产生的工具将被应用于微型飞行器有限的计算执行各种任务，如搜索，勘探，并在搜索和救援的情况下导航。这个奖项反映了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.