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

Princeton University, Princeton NJ

Investigators

Abstract

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.