Junlin Ou

Date of Award

Fall 2023

Document Type

Open Access Dissertation

Department

Mechanical Engineering

First Advisor

Yi Wang

Abstract

This research presents systematic studies and algorithmic and hardware development to enable real-time edge computing for autonomous systems, in particular, for robot path planning and localization applications. First, a low-cost, indoor, multi-camera positioning system is proposed to localize ground robots using the ArUco marker. In this system, the normalized coordinates of the marker processed by OpenCV are utilized to calculate the camera coordinates. Data-driven models are developed to establish a mapping relationship between the camera coordinates and the world coordinates of the marker. Fifty data pairs of the camera and world coordinate systems within one camera view (150 pairs in total for three cameras in our system) are collected to train and test the model. Various techniques, including rigid transformation, polynomial regression, artificial neural network, Kriging interpolation, and Kriging regression, are evaluated and compared in terms of positioning accuracy, ease of implementation, and robustness. When 40 data pairs are used for training, the polynomial regression method outperforms the others and achieves a positioning accuracy of about 1.5 cm. With only 10 data pairs for model training, rigid transformation, Kriging models, and hybrid models are superior. Further experiments are performed to verify that the developed indoor positioning system can reliably track the mobile robot in real time. The system pushes the limit of positioning accuracy from the algorithm and software perspective while minimizing the overall hardware and installation cost. Therefore, it is particularly appealing for robot research and education in resource-limited environments. Second, a global path planning framework based on genetic algorithm (GA) optimization on a highly parallelized Graphics Processing Unit (GPU) platform is developed for mobile robots. A method to randomly initialize waypoints in the free space near obstacle corners is proposed, which, in conjunction with a mutation in the free space, shows excellent advantages over other benchmark methods while maintaining salient computing performance. Besides, the migration process is introduced to GA to mitigate the issue of premature convergence. To determine the best GA configurations, a tradeoff analysis is conducted. It is found that the runtime is minimized, and optimization accuracy is preserved when the number of populations and individuals are selected as 640 and 64. The number of generations is selected as 1,000 according to the convergence rate of GA optimization. An objective function allowing differential consideration of the path length, smoothness, safety, and feasibility through individual weights is also presented. Numerical experiments demonstrate that different optimal paths can be obtained from the same map by tuning the weights. Compared to its serial CPU counterpart, the speedup achieved by GPU computing is 83×. Third, a new initialization method combining adaptive visibility graphs and Dijkstra’s algorithm is proposed to improve the exploration, accuracy, and computing efficiency of hybrid path planning for mobile robots. In this approach, segments/links in the full visibility graphs are first removed randomly in an iterative and adaptive manner, yielding adaptive visibility graphs. Then, Dijkstra’s algorithm is applied to find the shortest paths in these adaptive visibility graphs. Next, high-quality paths featuring low fitness values are chosen to initialize the subsequent heuristic optimization. Specifically, GA is implemented on a CPU/GPU edge computing device (Jetson AGX Xavier) to exploit its massively parallel processing threads, and the strategy for judicious CPU/GPU resource utilization is also proposed. Numerical experiments are conducted to determine proper hyperparameters to configure GA with balanced performance. Various optimal paths with different considerations of practical factors for robot path planning are attained by the proposed method. Compared to other methods, ours significantly improves the diversity of initial path and exploration, optimization accuracy, and computing speed (within 5 seconds with most less than 2 seconds). Furthermore, real-time experiments are carried out to demonstrate the effectiveness and real application of the proposed algorithm on mobile robots. Fourth, a novel initialization method for real-time robotic path planning in a dynamic environment (involving moving obstacles) is proposed. The innovation lies in the formulation of the path planning problem as a Markov decision process, the development of a new evolutionary dynamic programming (EDP) algorithm, and the integration of both onto a holistic platform for enhanced exploration, computation efficiency, and robustness. The new methodology features several key technological elements, including constructing a visibility graph, building the Markov decision process based on the visibility graph, executing EDP to find various initial paths with the largest state values, and optimizing each initial path parallelly and independently by GPU-enabled GA. The proposed algorithm is also implemented on an embedded edge computing device (Jetson AGX Xavier), and the approach to fully utilize CPU/GPU resources for EDP in the Markov decision process is determined for computational acceleration. The proposed method can generate an optimal path continuously at the rate of 0.1 seconds/path in dynamic environments. Experiments are conducted on a robotic platform, TurtleBot 3 Waffle Pi, to verify the real-time capabilities and accuracy of the proposed algorithm. In conclusion, the proposed indoor positioning system and path planning algorithms amenable to edge computing and decentralized decision-making in a dynamic environment are verified. The efforts also serve as a proven reference point for relevant research in this field. Future efforts will focus on consolidating and optimizing the algorithm execution efficiency, enhancing control strategies, incorporating motion estimation of obstacles for better obstacle avoidance, and multi-agent path planning.

Rights

© 2024, Junlin Ou

Download

Share

COinS