CRII:IIS:Topology Aware Configuration Spaces

点击翻译按钮获取中文摘要

Motion planning is an important concept in robotics with a simple definition - find a path for a robot from its start to a goal position, where the start and goal is determined by the task the robot is expected to perform e.g., navigate a factory floor, manipulate an arm to pick up an object etc. This however is difficult to model and compute. To efficiently plan motions neccessitates having complete information about the robot's environment beforehand, then building efficient algorithms that produces a trajectory the robot can utilize; unfortunately, this has proven difficult to achieve. To mitigate this shortcoming, sampling-based algorithms were developed that approximate the information given about the environment. Analysis of these algorithms shows that if a trajectory exists, these sampling algorithms will find such trajectory. The question that arises, though, is how well was the environment information approximated to ensure a high success rate. This project will develop algorithms that better approximate the environment information planning space by producing a measure for this approximation using topology and geometric based formulations. This project will give more control to sampling algorithms to help determine what areas in the environment needs more attention and representation, which will in turn improve on the time needed to perform motion planning.Motivated by the increasing need for motion planning algorithms that are fast and accurate even when they approximate the planning space, and a need to also measure such approximations so as to better manipulate and control the planning process, this project aims to devise a set of formal representations and algorithms to a) better characterize the topology of the planning space, b) combine formal methods to plan and approximate the planning space, c) provide a measure of such approximations and utilize this information to better guide planning in difficult regions, and d) subsequently reduce planning time and memory use which will potentially lead to more real time planning algorithms. In addition, the algorithms and theorems developed in this project will be adaptable to any planning method in any type of environment (dynamic, complex or heterogeneous). This research thus removes a major barrier in the current practice of motion planning where approximate techniques are the state of the art. This project will greatly increase the scalability of motion planning algorithms because it will be topologically rich with information, measure the sampling approximations made in the planning space, and subsequently give a more informed description of these planning spaces. This project will capture in a unique and novel way the topology of the planning space using mathematical formulations such as the Vietoris Rips complex, graph "gluing", and an innovative use of simplicial collapses in planning algorithms.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.