Autonomous navigation of mobile robots through unstructured terrain presents many challenges. The task becomes even more difficult with increasing obstacle density, at higher speeds, and when a priori knowledge of the terrain is not available. Reactive navigation schemas are often dismissed as overly simplistic or considered to be inferior to deliberative approaches for off-road navigation. The Potential Field algorithm has been a popular reactive approach for low speed, highly maneuverable mobile robots. However, as vehicle speeds increase, Potential Fields becomes less effective at avoiding obstacles. The traditional shortcomings of the Potential Field approach can be largely overcome by using dynamically expanding perception zones to help track objects of immediate interest. This newly developed technique is hereafter referred to as the Dynamic Expanding Zones (DEZ) algorithm. In this approach, the Potential Field algorithm is used for waypoint navigation and the DEZ algorithm is used for obstacle avoidance. This combination of methods facilitates high-speed navigation in obstacle-rich environments at a fraction of the computational cost and complexity of deliberative methods. The DEZ reactive navigation algorithm is believed to represent a fundamental contribution to the body of knowledge in the area of high-speed reactive navigation. This method was implemented on the Virginia Tech DARPA Grand Challenge vehicles. The results of this implementation are presented as a case study to demonstrate the efficacy of the newly developed DEZ approach. / Master of Science

We study the problem of planning a tour for an energy-limited Unmanned Aerial Vehicle (UAV) to visit a set of sites in the least amount of time. We envision scenarios where the UAV can be recharged along the way either by landing on stationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting as mobile recharging stations. This leads to a new variant of the Traveling Salesperson Problem (TSP) with mobile recharging stations. We present an algorithm that finds not only the order in which to visit the sites but also when and where to land on the charging stations to recharge. Our algorithm plans tours for the UGVs as well as determines the best locations to place stationary charging stations. While the problems we study are NP-Hard, we present a practical solution using Generalized TSP that finds the optimal solution. If the UGVs are slower, the algorithm also finds the minimum number of UGVs required to support the UAV mission such that the UAV is not required to wait for the UGV. We present a calibration routine to identify parameters that are needed for our algorithm as well as simulation results that show the running time is acceptable for reasonably sized instances in practice. We evaluate the performance of our algorithm through simulations and proof-of-concept experiments with a fully autonomous system of one UAV and UGV. / Master of Science / Commercially available Unmanned Aerial Vehicles (UAVs), especially multi-rotor aircrafts, have a flight time of less than 30 minutes. However many UAV applications, such as surveillance, package delivery, and infrastructure monitoring, require much longer flight times. To address this problem, we present a system in which an Unmanned Ground Vehicle (UGV) can recharge the UAV during deployments. This thesis studies the problem of finding when, where, and how much to recharge the battery. We also allow for the UGV to recharge while moving from one site to another. We present an algorithm that finds the paths for the UAV and UGV to visit a set of points of interest in the least time possible. We also present algorithms for cases when the UGV is slower than the UAV, and more than one UGV may be required. We evaluate our algorithms through simulations and proof-of-concept experiments.

Students at Virginia Tech have been developing autonomous vehicles for the past five years. The purpose of these vehicles has been primarily for entry in the annual international Intelligent Ground Vehicle Competition (IGVC), however further applications for autonomous vehicles range from UneXploded Ordinance (UXO) detection and removal to planetary exploration. Recently, Virginia Tech developed a successful autonomous vehicle named Navigator. Navigator was developed primarily for entry in the IGVC, but also intended for use as a research platform. For navigation, Navigator uses a local obstacle avoidance method known as the Vector Field Histogram (VFH). However, in order to form a complete navigation scheme, the local obstacle avoidance algorithm must be coupled with a global map. This work presents a simple algorithm for developing a quasi-free space global map. The algorithm is based on the premise that the robot will be given multiple attempts at a particular goal. During early attempts, Navigator explores using solely local obstacle avoidance. While exploring, Navigator records where it has been and uses this information on subsequent attempts. Further, this thesis outlines the look-ahead method by which the global map is implemented. Finally, both simulated and experimental results are presented. The aforementioned global map building algorithm uses a common method of localization known as odometry. Odometry, also referred to as dead reckoning, is subject to inaccuracy caused by systematic and non-systematic errors. In many cases, the most dominant source of inaccuracy is systematic errors. Systematic errors are inherent to the vehicle; therefore, the dead reckoning inaccuracy grows unbounded. Fortunately, it is possible to largely eliminate systematic errors by calibrating the parameters such that the differences between the nominal dimensions and the actual dimensions are minimized. This work presents a method for calibration of mobile robot parameters using optimization. A cost function is developed based on the well-known UMBmark (University of Michigan Benchmark) test pattern. This method is presented as a simple time efficient calibration tool for use during startup procedures of a differentially driven mobile robot. Results show that this tool consistently gives greater than 50% improvement in overall dead reckoning accuracy on an outdoor mobile robot. / Master of Science

The implementation of deep reinforcement learning in mobile robotics offers a great solution for the development of autonomous mobile robots to efficiently complete tasks and transport objects. Reinforcement learning continues to show impressive potential in robotics applications through self-learning and biological plausibility. Despite its advancements, challenges remain in applying these machine learning techniques in dynamic environments. This thesis explores the performance of Deep Q-Networks (DQN), using images as an input, for mobile robot navigation in dynamic maze puzzles and aims to contribute to advancements in deep reinforcement learning applications for simulated and real-life robotic systems. This project is a step towards implementation in a hardware-based system. The proposed approach uses a DQN algorithm with experience replay and an epsilon-greedy annealing schedule. Experiments are conducted to train DQN agents in static and dynamic maze environments, and various reward functions and training strategies are explored to optimize learning outcomes. In this context, the dynamic aspect involves training the agent on fixed mazes and then testing its performance on modified mazes, where obstacles like walls alter previously optimal paths to the goal. In game play, the agent achieved a 100\% win rate in both 4x4 and 10x10 static mazes, successfully making it to the goal regardless of slip conditions. The number of rewards obtained during the game-play episodes indicates that the agent took the optimal path in all 100 episodes of the 4x4 maze without the slip condition, whereas it took the shortest, most optimal path in 99 out of 100 episodes in the 4x4 maze with the slip condition. Compared to the 4x4 maze, the agent more frequently chose sub-optimal paths in the larger 10x10 maze, as indicated by the amount of times the agent maximized rewards obtained. In the 10x10 static maze game-play, the agent took the optimal path in 96 out of 100 episodes for the no slip condition, while it took the shortest path in 93 out of 100 episodes for the slip condition. In the dynamic maze experiment, the agent successfully solved 7 out of 8 mazes with a 100\% win rate in both original and modified maze environments. The results indicate that adequate exploration, well-designed reward functions, and diverse training data significantly impacted both training performance and game play outcomes. The findings suggest that DQN approaches are plausible solutions to stochastic outcomes, but expanding upon the proposed method and more research is needed to improve this methodology. This study highlights the need for further efforts in improving deep reinforcement learning applications in dynamic environments.

A distributed reinforcement-learning system is designed and implemented on a mobile robot for the study of complex task decomposition in real robot learning environments. The Distributed Q-learning Classifier System (DQLCS) is evolved from the standard Learning Classifier System (LCS) proposed by J.H. Holland. Two of the limitations of the standard LCS are its monolithic nature and its complex apportionment of credit scheme, the bucket brigade algorithm (BBA). The DQLCS addresses both of these problems as well as the inherent difficulties faced by learning systems operating in real environments. We introduce Q-learning as the apportionment of credit component of the DQLCS, and we develop a distributed learning architecture to facilitate complex task decomposition. Based upon dynamic programming, the Q-learning update equation is derived and its advantages over the complex BBA are discussed. The distributed architecture is implemented to provide for faster learning by allowing the system to effectively decrease the size of the problem space it must explore. Holistic and monolithic shaping approaches are used to distribute reward among the learning modules of the DQLCS in a variety of real robot learning experiments. The results of these experiments support the DQLCS as a useful reinforcement learning paradigm and suggest future areas of study in distributed learning systems. / Master of Science

Research in the area of autonomous mobile robots has increased over the last several years. Autonomous mobile robots are now being used in a wide variety of applications, including nuclear plant maintenance, interplanetary exploration, military missions and smart highway systems. This thesis is a survey of recent publications, 1990-1996, of wheeled autonomous mobile robots for harsh environments. Various sensing, navigation, and motion control strategies commonly used on autonomous mobile robots are compared. The integration of all three systems in a system architecture is also presented. Following a general discussion of autonomous mobile robot technology, vehicles that have entered the Unmanned Ground Robotics Competition are presented as a focused study of the application of this broad field of research. / Master of Science

Adaptive controllers allow robots to perform a wide variety of tasks, but the extensive computations required have generated an interest in developing decentralized adaptive controllers. Horner has designed an adaptive controller for a four-degree-of-freedom mobile robot and tested it through simulations. The study described in this thesis uses the techniques described by Horner to design and test a decentralized model reference adaptive controller (DMRAC) for a physical four-degree-of-freedom mobile robot. The study revealed several difficulties in implementing this design. Most notably, the robot available for the research did not allow for the measurement of joint velocity, so it was necessary to estimate the velocity as the derivative of the position measurement. The noise created by this estimation made completion of testing impossible. Future research should be performed on a robot that provides joint velocity measurement. Alternatively, a study could include state estimation as part of the controller, thus reducing and possibly eliminating the need for velocity measurement. / Master of Science

Wireless communication provides an effective means by which mobile robots can be operated, field tested, and trained remotely. This thesis explores a design that is intended to simplify the process of creating communication software for these and other similar purposes. The proposed software is responsible for generating client-server modules that are able to be readily loaded into any number of wirelessly connected mobile robots and handheld devices. In general, the system is designed to be low-cost, simple to use, and robust, with particular design considerations for software portability and modularity. Portability is obtained by using the Java™ platform and modularity is obtained by incorporating object-oriented design. The test platform for this system is comprised of a Palm OS® handheld device, a Linux-based mobile robot, and a wireless Ethernet connection.

A nonholonomic tracking controller is designed and adapted to work with both differential steering and Ackermann steering based platforms whose dynamics are represented using a unicycle model. The goal of this work is to find a relatively simple approach that offers a practical alternative to bulky and expensive algorithms, but still bolsters applicability where many other lightweight algorithms are too lax. The hope is that this alternative will offer a straightforward approach for groups interested in autonomous vehicle research but who do not have the resources or personnel to implement more complex solutions. In the first phase of this work, saturation constraints based on differential drive kinematics are added to ensure that the vehicle behaves intuitively and does not exceed user defined limitations. A new strategy for mapping commands back into a viable envelope is introduced, and the restrictions are accounted for using Lyapunov stability criteria. This stage of work is validated through simulation and experimentation. Following the development of differential drive methods, similar techniques are applied to Ackermann steering kinematic constraints. An additional saturation algorithm is presented, which likewise is accounted for using Lyapunov stability criteria. As with the differential case, the Ackermann design is validated through simulation and experimentation. Overall, the results presented in this work demonstrate that the developed algorithms show significant promise and offer a lightweight, practical solution to the problem of vehicle tracking control. / Master of Science / In this work, a position controller for ground vehicles is developed. The algorithm takes into account the constraints of both Ackermann and differential drive platforms. A simplistic model is used for the initial development of this control algorithm, and more rigid constraints are added based on the intended platform. The goal of this work is to find a relatively simple approach that offers a practical alternative to bulky and expensive algorithms, but still bolsters applicability where many other lightweight algorithms are too lax. The hope is that this alternative will offer a straightforward approach for groups interested in autonomous vehicle research, but who do not have the resources or personnel to implement more complex solutions. Throughout this work, we present the theoretical development as well as simulation and experiments to verify the efficacy of our approach. Overall, the results presented in this work demonstrate that the developed algorithms show significant promise and offer a lightweight, practical solution to the problem of vehicle tracking control.

In urban search and rescue (USAR) operations, there is a considerable amount of danger faced by rescuers. The use of mobile robots can alleviate this issue. Coordinating the search effort is made more difficult by the communication issues typically faced in these environments, such that communication is often restricted. With small numbers of robots, it is necessary to break communication links in order to explore the entire environment. The robots can be viewed as a broken ad hoc network, relying on opportunistic contact in order to share data. In order to minimise overheads when exchanging data, a novel algorithm for data exchange has been created which maintains the propagation speed of flooding while reducing overheads. Since the rescue workers outside of the structure need to know the location of any victims, the task of finding their locations is two parted: 1) to locate the victims (Search Time), and 2) to get this data outside the structure (Delay Time). Communication with the outside is assumed to be performed by a static robot designated as the Command Station. Since it is unlikely that there will be sufficient robots to provide full communications coverage of the area, robots that discover victims are faced with the difficult decision of whether they should continue searching or return with the victim data. We investigate a variety of search techniques and see how the application of biological foraging models can help to streamline the search process, while we have also implemented an opportunistic network to ensure that data are shared whenever robots come within line of sight of each other or the Command Station. We examine this trade-off between performing a search and communicating the results.