Recent Advances In Robot Path Planning Algorithms A Review Of Theory And Experiment PDF Download

The mission of this thesis is to develop algorithms for planning and control of intelligent mobile robots that operate autonomously in open, interactive environments. Presence of other agents and objects in such an environment makes planning significantly challenging, as they inevitably bring about environmental and dynamic uncertainty that the robot must properly handle. Despite recent advances in perception, planning and control, many existing robotic systems to date lack the capability to consider and address uncertainty, which demands that the robots be caged or confined to a dedicated, structured workspace. For example, success of thousands of mobile robots nowadays deployed in logistics centers is heavily reliant on their closed and controlled operating environments. In this thesis, we propose a series of computationally efficient algorithms that can collectively overcome uncertainty of various sources towards reliable autonomy for "cage-free" robotic operations. The methods presented in the thesis leverage probability theory to quantify the amount of present and future uncertainty. Based on the quantification, we develop planning and control algorithms that either mitigate, avoid the risk of, or are robust against uncertainty so that the robot can successfully accomplish a given task. We take a model-based approach in developing those algorithms, which allows us to exploit physical properties of dynamical systems and onboard sensors when possible. Another crucial aspect of the proposed methods is their online nature, meaning that control signals are computed in situ based on the currently available information. This is enabled by fast, efficient computation of our algorithms, and is advantageous in that the robot can quickly react to rapidly changing environments. In the first part of the thesis, we address challenges associated with state uncertainty, which represents unknowns about the current state of the system of interest. This can include unknown intent of other interacting agents, or positions of targets to locate. We propose and employ recursive Bayesian inference frameworks to keep track of evolving state uncertainty over time. The proposed planning algorithms further assist the inference frameworks to actively mitigate state uncertainty as appropriate, so that the robot can execute suitable control actions with certainty. We leverage tools from sequential decision-making and optimal control to develop those algorithms. We demonstrate the effectiveness of our approach in a multitude of tasks that involve state uncertainty, with different combinations of dynamical systems and sensing modalities. This includes vision-based active intent inference, active target tracking with range-only observations, and simultaneous object manipulation and parameter estimation. We then turn our attention to transition uncertainty, which governs the unpredictability of future states of the system. We especially focus on safety-critical problems where transition uncertainty must not be ignored. For instance, a robot navigating in close proximity to humans has to carefully perform planning so that collisions are avoided with high confidence. We take a risk-aware planning approach, in which a risk metric that takes into account the variance of uncertainty is to be optimized. While being computationally efficient, our proposed method does not require knowledge of the analytical form of the underlying probability distribution that quantifies transition uncertainty, nor is it limited to a certain class of distributions such as Gaussian. This atypical feature enables us to leverage modern data-driven generative models for uncertainty quantification. We demonstrate the applicability of our approach to the aforementioned robot navigation task, where we show that the proposed framework can safely navigate the robot towards its goal while interacting with more than 50 humans simultaneously in real time. Moreover, our risk-aware formulation is demonstrated to promote safety in both simulation and a real-world experiment, by inducing a proactive robot behavior that avoids risky situations where high variance of uncertainty could lead to imminent collision. The last part of this thesis considers model uncertainty, which is attributed to imperfect modeling of the underlying stochastic phenomena. Our approach makes the planner distributionally robust, in which the planner selects a control policy that acts against a worst-case distribution within an offline-computed set of plausible distributions that could quantify transition uncertainty. We develop a tractable algorithm leveraging mathematical equivalence between risk-aware planning and distributionally robust planning. We show in simulation that the proposed planning framework can safely avoid collision despite imperfect knowledge of the stochastic human motion model. Furthermore, our approach lets the risk-aware planner dynamically adjust the level of risk-sensitivity online, which further improves the flexibility of conventional risk-aware planning methods. The algorithms developed in this thesis will ultimately allow intelligent mobile robots to operate in considerably more uncertain and dynamic workspaces than the current industrial standard. This will open up possibilities for various practical applications, including autonomous field robots for persistent environmental monitoring, fully-automated driving on urban roads, and autonomous drone flights in densely populated areas for logistics services. We believe that such "cage-free" robotic operations will be enabled by proper consideration and treatment of uncertainty, and that our methods will pave the way towards more reliable robotic autonomy in open and interactive environments.