Robust target tracking and navigation for mobile robots with guaranteed performance

Abstract

Research on mobile robot includes a wide range of research elds such as path planning, target tracking, and navigation. Since these elds deal with the fundamental and necessary technologies for mobile robots, they have been actively investigated for a long period of time. Nonetheless, such algorithms have not been sufficiently developed to deploy the robot in the real environments, since the real world is uncontrolled, complicated and variable. The complex environments generate various uncertainties which can result in different consequences from the intent of the algorithm. Hence, uncertainties can lead to failure of navigation algorithms which do not take uncertainties into account. The most representative example of uncertainties is the uncertainty in the dynamic model of the robot. In general, the dynamic model of the robot is given, when we solve the navigation problem such as a path planning problem. Unfortunately, in the real world, there can be uncertainties caused by disturbances such as friction or air flow. Since the uncertainties can make the planned trajectory infeasible, it is necessary to develop a control algorithm with a high probability of success considering uncertainties. Another example is the uncertainties in motion of objects near the robot. When the robot tracks an object or avoids the obstacles, it is important to predict their motion. However, even if the prediction algorithm is quite accurate, it cannot be deterministic and uncertainties exists in the predicted value. Therefore, we need to develop a controller that is robust against uncertainties. In this dissertation, we propose robust target tracking algorithms and path planning algorithms under uncertainties. The target tracking problem aims to locate the target within the nite and fan-shaped sensing region of the robot when the motion of the target is predictable as a Gaussian distribution. We formulate a non-convex optimization problem such that the solution is the control which maximizes the success probability of tracking and minimizes the moving distance of the robot. The optimization can be solved in real time by dividing the problem into several convex problems and solving them analytically. The proposed method is successfully applied to 2D and 3D mobile robots and shows the robustness against uncertainties by guaranteeing the success probability. For more general applications, we extend the tracking algorithm to consider identity uncertainties when multiple objects are detected in the sensing region. We predict the motion of the target as a Gaussian mixture model using a multiple-hypothesis prediction algorithm which combines the motion model and the appearance model of the target. Then we propose the control which maximizes the success probability of tracking. If the success probability is guaranteed as a suciently high value, the control minimizes the moving distance of the robot. We also focus on a more complicated problem which is path planning to generate a long-period trajectory while target tracking generates a one-step control. The proposed path planning algorithm searches a trajectory which satises mission requirements specied in linear temporal logic (LTL). Since the robot does not follow the exact planned trajectory with a high probability due to uncertainties in its dynamic model, it can fail to accomplish the mission or collide with obstacles. For safety and robustness under uncertainties, we propose a multi-layered sampling based path planning, where a high-level planner generates a discrete trajectory to guide a low-level planner and the low-level planner generates a safe and robust trajectory to accomplish the mission. Our algorithm has the advantage of limiting the probability of collision below a certain threshold and increasing the probability of success. The method is extended to path planning algorithms under time-varying uncertainties. The proposed methods in this dissertation represent the uncertainty a