Searching, algorithms and complexity

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

This proposal for research in Computer Science deals with parallel computing and complexity as applied to problems in the area of multi-agent mobile robotics. The challenge of computing using parallel computers now faces almost every area of computing. Past economic advances due to progress in computing have depended in large part on continuing improvements in individual processor speeds, but processor speeds are no longer increasing as rapidly as before. Instead, computing in parallel is becoming the main direction for progress. The challenge is to make effective use of parallel hardware in many new contexts. The research proposed here is principally focused on parallel and distributed computing problems that are related to mobile robotics. This area of research focuses on finding methods for using multiple moving robots. (1) The simultaneous location and mapping (SLAM) problem deals with the question of "where am I'' for robots trying to create a map of their local world. This problem is important for the deployment of robots in unknown environments, such as unexplored terrain or severely hazardous locations. We will study sensor requirements and algorithms needed to solve this SLAM problem in different environments. (2) Leader election is another key problem in distributed computing, important as a basis for many other problems. We consider a set of independent robots with very limited communication capabilities, each one executing an algorithm in order for them together to jointly complete some task. We will further develop methods for the agents to quickly find a leader, and other basic tasks, by simple one-to-one communications when they meet, even not knowing the actual number of robots involved. (3) High-dimensional robot path planning is important in moving robots to perform tasks. We plan work on a probabilistic approach to this problem. One place where this could be used is planning motions necessary to efficiently move a complicated tentacle-like robot arm with many joints.