RI: Small: Incremental Sampling-Based Algorithms and Stochastic Optimal Control on Random Graphs

自主和半自动车辆和系统在民用（消防、核废料处理、执法、深海勘探和钻探、天气预报、运输）和军事（制导导弹、航天器、无人驾驶飞机）应用中都不可或缺。自动化与信息技术相结合，将继续以越来越高的水平渗透我们的社会。到目前为止，自主系统一直是国土安全应用（例如边境巡逻、持续监控等）的关键组成部分，现在被视为赋予人们日常生活中工作、休闲和家庭任务的关键因素。下一代自主系统将在家庭或办公室与人类进行操作和互动。亚马逊（Amazon）和b谷歌等信息技术公司最近在机器人技术方面的投资，可能会加速公众对这些新技术的采用。所有这些自主系统的安全可靠运行，关键取决于它们对环境进行推理和导航的能力。本研究中开发的理论和方法将使在这些自主系统的“大脑”中运行高度复杂的算法成为可能，从而实现最佳决策，从而提高其可靠性、可预测性、性能和故障安全操作。自动驾驶汽车、拟人化机器人、无人机、制造自动化系统和精密手术器械等都将受益于这项研究的成果。提出的研究解决了机器人和智能自主系统运动规划和轨迹生成领域的一个基本问题。在有限的资源约束（例如，计算机内存，时间）下解决此类问题的一个严重瓶颈是它们的高维性，这排除了naïve使用离散（连续）状态空间。在本研究中，提出了一种新的基于增量的、最优采样的运动规划算法，该算法在现有方法的基础上具有更高的收敛速度，从而为在不确定和动态变化的环境中运行的自动驾驶汽车提供接近实时的轨迹生成。为了实现这一目标，本研究将基于快速探索随机图（RRG）的最新成果和想法，以及从异步动态规划（ADP）和机器学习（ML）领域借鉴的放松方法。具体来说，机器学习的最新进展可以用来解决三个主要问题，这些问题阻碍了基于概率采样的运动规划器在更广泛的问题上的更广泛的适用性：碰撞检查、有效采样和局部转向。所提出的研究的一个主要原则是利用所提出算法的固有并行性，再加上多核计算机体系结构和gpu的最新进展，将实现实时计算。

Autonomous and semi-autonomous vehicles and systems have become indispensable both for civil (fire-fighting, nuclear waste handling, law-enforcement, deep ocean exploration and drilling, weather forecasting, transportation) and military (guided missiles, spacecraft, unmanned drones) applications. Automation, when coupled with information technology, will continue to permeate our society at ever increasing levels. Autonomous systems, which, thus far, have been a crucial component in homeland security applications (e.g., border patrol, persistent monitoring, etc), are now seen as a key factor of empowering people in their daily lives across work, leisure, and domestic tasks. The next generation of autonomous systems will operate and interact with humans in the household or the office. The recent investment of information technology companies such as Amazon and Google in robotics technology is likely to accelerate the adoption of these new technologies by the general public. The safe and reliable operation of all these autonomous systems hinges crucially on their ability to reason and navigate about their environment. The theory and methodologies developed in this research will make it possible to run highly sophisticated algorithms inside the "brain" of these autonomous systems to enable optimal decision-making, thus increasing their reliability, predictability, performance and fail-safe operation. Self-driving vehicles, anthropomorphic robots, aerial drones, manufacturing automation systems, and precision surgical instruments among others, will all benefit from the results of this research.The proposed research tackles a fundamental problem in the area of motion planning and trajectory generation for robotic and intelligent autonomous systems. A serious bottleneck in solving such problems under limited resource constraints (e.g., computer memory, time) is their high dimensionality that precludes the naïve use of discretizing the (continuous) state space. In this research it is proposed to develop new incremental, optimal sampling-based motion planning algorithms with improved convergence rates over existing methods, so as to enable close-to-real-time trajectory generation for autonomous vehicles operating in an uncertain and dynamically changing environment. To achieve this objective, this research will build on recent results and ideas from Rapidly-exploring Random Graphs (RRG), along with relaxation methods borrowed from the areas of Asynchronous Dynamic Programming (ADP) and Machine Learning (ML). Specifically, recent advances from machine learning can be used to address the three main issues hindering the broader applicability of probabilistic sampling based motion planners to a wider variety of problems: collision checking, efficient sampling, and local steering. One main tenet of the proposed research is the exploitation of the inherent parallelism of the proposed algorithms, which -- coupled with the recent advances in multi-core computer architectures and GPUs -- will enable real-time computations.