Searching, algorithms and complexity

搜索、算法和复杂性

• 批准号: 124570-2013
• 负责人: Dymond, Patrick
• 金额: $ 1.09万
• 依托单位: York University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2013
• 资助国家: 加拿大
• 起止时间: 2013-01-01 至 2014-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=522295
• 关键词: Searching; algorithms; 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.

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