Searching, algorithms and complexity

本计算机科学研究计划涉及应用于多智能体移动机器人领域的并行计算和复杂性问题。使用并行计算机进行计算的挑战现在几乎面临着计算的每个领域。过去由于计算技术的进步而取得的经济进步在很大程度上依赖于单个处理器速度的不断提高，但是处理器速度的提高不再像以前那么快了。相反，并行计算正在成为发展的主要方向。挑战在于如何在许多新环境中有效地使用并行硬件。这里提出的研究主要集中在与移动机器人相关的并行和分布式计算问题上。这一领域的研究重点是寻找使用多个移动机器人的方法。(1)同时定位和映射（SLAM）问题处理的是机器人试图创建其本地世界地图的“我在哪里”问题。这个问题对于在未知环境中部署机器人非常重要，例如未探索的地形或严重危险的位置。我们将研究在不同环境下解决该SLAM问题所需的传感器要求和算法。(2) Leader选举是分布式计算中的另一个关键问题，是许多其他问题的重要基础。我们考虑一组独立的机器人，它们的通信能力非常有限，每个机器人都执行一种算法，以便它们共同完成一些任务。我们将进一步开发方法，让agent在不知道实际参与的机器人数量的情况下，通过简单的一对一交流，快速找到领导者和其他基本任务。(3)高维机器人路径规划是运动机器人执行任务的重要手段。我们计划用概率方法来解决这个问题。其中一个应用领域是规划必要的运动，以有效地移动一个复杂的、像触角一样的、有许多关节的机器人手臂。

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.