The current state of 3D path-planning leaves room for improvement. To navigate a 3D environment, techniques which were developed for 2D navigation are used and slightly adapted to generate convincing motion. However, these techniques often constrict the motion to a single plane. This constriction is not only a limitation, but also increases the error. We created a new method to compute a path in a 3D world without a planar constraint. We will discuss the computation of a Navigation Volume Network (NavNet), and how it finds a path. A NavNet is the 3D generalization of NavMeshes, and holds boundary and connection information which is utilized when planning a path for motion. Similar to how NavMeshes allow path-planning by simplifying the ground meshes, the NavNet simplifies the search space by approximating the 3D world through sampling. / Thesis / Master of Applied Science (MASc)

In this dissertation, we seek to improve and advance the use of the finite-set statistics (FISST) approach to multitarget tracking. We consider a subsea multitarget tracking application that poses several challenges due to factors, such as, clutter/environmental noise, joint target and sensor state dependent measurement uncertainty, target-measurement association ambiguity, and sub-optimal sensor placement. The specific application that we consider is that of an underwater mobile sensor that measures the relative angle (i.e., bearing angle) to sources of acoustic noise in order to track one or more ships (targets) in a noisy environment. However, our contributions are generalizable for a variety of multitarget tracking applications. We build upon existing algorithms and address the problem of improving tracking performance for multiple maneuvering targets by incorporation several target motion models into a FISST tracking algorithm known as the probability hypothesis density filter. Moreover, we develop a novel method for associating measurements to targets using the Bayes factor, which improves tracking performance for FISST methods as well as other approaches to multitarget tracking. Further, we derive a novel formulation of Bayes risk for use with set-valued random variables and develop a real-time planner for sensor motion that avoids local minima that arise in myopic approaches to sensor motion planning. The effectiveness of our contributions are evaluated through a mixture of real-world and simulated data. / Doctor of Philosophy / In this dissertation, we seek to improve the accuracy of multitarget tracking algorithms based on finite-set statistics (FISST). We consider a subsea tracking application where a sensor seeks to estimate the position of nearby ships using measurements of the relative sensor-ship angle. Several challenges arise in our application due to factors such as environmental noise and limited resolution of measurements. Our work advances FISST algorithms by expanding upon existing methods and deriving novel solutions to mitigate challenges. We address the non-trivial question of improving tracking accuracy by planning of future sensor motion. We show that our contributions greatly improve tracking accuracy by evaluating algorithm performance using a mixture of real-world and simulated data.

In the context of path planning, the non-signalized intersections are always a challenging scenario due to the mixture of traffic flow. Most path planning algorithms use the information at the current time instance to generate an optimal path. Because of the dynamics of the non-signalized intersections, iteratively generating a path in a high frequency is necessary, resulting in an enormous waste of computational resources. Rapidly-exploring Random Tree (RRT) as an effective local path planning methodology can determine a feasible path in the static environment. Few improvements are proposed to adopt the RRT to the non-signalized intersections. Gaussian Processes Regression (GPR) is used to predict the other vehicles' future location. The location information in the current and future time instance is used to generate a probability position map. The map not only avoids useless sampling procedures but also increases the speed of generating a path. The optimal steering strategy is deployed to guarantee the trajectory is collision-free in both current and future time frames. Overall, the proposed probabilistic RRT algorithm can select a collision-free path in the non-signalized intersections by combining the GPR, probability position map, and optimal-steering. / Master of Science / Path planning problem is a challenge in the non-signalized intersections. Many path planning algorithms can generate an optimal path in the space domain but not in the time domain. Thus, the algorithms need to run iteratively at a high frequency to ensure the path's optimality in the time domain. By combining prediction and the standard RRT path planning algorithm, the resulting path ensures to be optimal in the space and time domain.

We study an informative path planning problem where the goal is to minimize the time required to learn a spatial field. Specifically, our goal is to ensure that the mean square error between the learned and actual fields is below a predefined value. We study three versions of the problem. In the placement version, the objective is to minimize the number of measurement locations. In the mobile robot version, we seek to minimize the total time required to visit and collect measurements from the measurement locations. A multi-robot version is studied as well where the objective is to minimize the time required by the last robot to return back to a common starting location called depot. By exploiting the properties of Gaussian Process regression, we present constant-factor approximation algorithms that ensure the required guarantees. In addition to the theoretical results, we also compare the empirical performance using a real-world dataset with other baseline strategies. / M. S. / We solve the problem of measuring a physical phenomenon accurately using a team of robots in minimum time. Examples of such phenomena include the amount of nitrogen present in the soil within a farm and concentration of harmful chemicals in a water body etc. Knowing accurately the extent of such quantities is important for a variety of economic and environmental reasons. For example, knowing the content of various nutrients in the soil within a farm can help the farmers to improve the yield and reduce the application of fertilizers, the concentration of certain chemicals inside a water body may affect the marine life in various ways. In this thesis, we present several algorithms which can help robots to be deployed efficiently to quantify such phenomena accurately. Traditionally, robots had to be teleoperated. The algorithms proposed in this thesis enable robots to work more autonomously.

Natural disasters damage infrastructure and create significant obstacles to humanitarian aid efforts. Roads may become unusable, hindering or halting efforts to provide food, water, shelter, and life-saving emergency care. Finding a safe route during a disaster is especially difficult because as the disaster unfolds, the usability of roads and other infrastructure can change quickly, rendering most navigation services useless. With the proliferation of cheap cameras and unmanned aerial vehicles [UAVs], the rapid collection of aerial data after a natural disaster has become increasingly common. This data can be used to quickly appraise the damage to critical infrastructure, which can help solve navigational and logistical problems that may arise after the disaster. This work focuses on a framework in which a UAV is paired with an unmanned ground vehicle [UGV]. The UAV follows the UGV with a downward-facing camera and helps the ground vehicle navigate the flooded environment. This work makes several contributions: a simulation environment is created to allow for automated data collection in hypothetical disaster scenarios. The simulation environment uses real-world satellite and elevation data to emulate natural disasters such as floods. The environment partially simulates the dynamics of the UAV and UGV, allowing agents to ex- plore during hypothetical disasters. Several semantic image segmentation models are tested for efficacy in identifying obstacles and creating cost maps for navigation within the environ- ment, as seen by the UAV. A deep homography model incorporates temporal relations across video frames to stitch cost maps together. A weighted version of a navigation algorithm is presented to plan a path through the environment. The synthesis of these modules leads to a novel framework wherein a UAV may guide a UGV safely through a disaster area. / Master of Science / Damage to infrastructure after a natural disaster can make navigation a major challenge. Imagine a hurricane has hit someone's house; they are hurt and need to go to the hospital. Using a traditional GPS navigation system or even their memory may not work as many roads could be impassible. However, if the GPS could be quickly updated as to which roads were not flooded, it could still be used to navigate and avoid hazards. While the system presented is designed to work with a self-driving vehicle, it could easily be extended to give directions to a human. The goal of this work is to provide a system that could be used as a replacement for a GPS based on aerial photography. The advantage of this system is that flooded or damaged infrastructure can be identified and avoided in real-time. The system could even identify other possible routes by using photography, such as driving across a field to reach higher ground. Like a GPS, the system works automatically, tracking a user's position and sug- gesting turns, aiding navigation. A contribution of this work is a simulation of the environment designed in a video game engine. The game engine creates a video game world that can be flooded and used to test the new navigation system. The video game environment is used to train an artificial intel- ligence computer model to identify hazards and create routes that would avoid them. The system could be used in a real-world disaster following training in a video game world.

Underwater gliders are robust and long endurance ocean sampling platforms that are increasingly being deployed in coastal regions. This new environment is characterized by shallow waters and significant currents that can challenge the mobility of these efficient (but traditionally slow moving) vehicles. This dissertation aims to improve the performance of shallow water underwater gliders through path planning. The path planning problem is formulated for a dynamic particle (or "kinematic car") model. The objective is to identify the path which satisfies specified boundary conditions and minimizes a particular cost. Several cost functions are considered. The problem is addressed using optimal control theory. The length scales of interest for path planning are within a few turn radii. First, an approach is developed for planning minimum-time paths, for a fixed speed glider, that are sub-optimal but are guaranteed to be feasible in the presence of unknown time-varying currents. Next the minimum-time problem for a glider with speed controls, that may vary between the stall speed and the maximum speed, is solved. Last, optimal paths that minimize change in depth (equivalently, maximize range) are investigated. Recognizing that path planning alone cannot overcome all of the challenges associated with significant currents and shallow waters, the design of a novel underwater glider with improved capabilities is explored. A glider with a pneumatic buoyancy engine (allowing large, rapid buoyancy changes) and a cylindrical moving mass mechanism (generating large pitch and roll moments) is designed, manufactured, and tested to demonstrate potential improvements in speed and maneuverability. / Ph. D.

In robotics, path planning refers to the process of establishing paths for robots to move from initial positions to goal positions without colliding into any obstacle within specified environments. Constructing roadmaps and searching for paths in the roadmaps is one of the most commonly used methodologies adopted in path planning. However, most sampling-based path planners focus on improving the speed of constructing roadmaps without taking into account the quality. Therefore, they often produce poor-quality roadmaps. Poor-quality roadmaps can cause problems, such as time-consuming path searches, poor quality path production, and even failure of the searching. This research aims to develop a novel sampling-based path planning algorithm which is able to incrementally construct high-quality roadmaps while answering path queries for robots with many degrees of freedom. A novel K-order surrounding roadmap (KSR) concept is proposed in this research based on a thorough investigation into the criteria of high-quality roadmaps, including the criteria themselves and the relationships between them. A KSR contains K useful cycles. There exist a value T for which we can say, with confidence, that the KSR is a high quality roadmap when K=T. A new sampling-based path planning algorithm, known as the KSR path planner that is able to construct a roadmap incrementally while answering path queries, is also developed. The KSR path planner can be employed to answer path queries without requiring any pre-processing. The planner grows trees from the initial and goal III configurations of a path query and connects these two trees to obtain a path. The path planner retains useful vertices of the trees and uses these to construct the roadmap and adds useful cycles to the existing roadmap in order to improve the quality. The roadmap constructed can be used to answer further queries. With the KSR path planner algorithm, there is no need to calculate the value of K to construct a high quality roadmap in advance. The quality of the roadmap improves as the KSR path planner answer queries until the roadmap is able to answer any path queries and no further useful cycles can be added into the roadmap. If the number of path queries is infinite, a high quality KSR can be constructed. The novelty of this KSR path planner is twofold. Firstly, it employs a vertex category classifier to understand local environments where roadmap vertices reside. The classifier is developed using a decision tree method. The classifier is able to classify vertices in a roadmap based on the region information stored in the vertices and their neighbours within a certain distance. The region information stored in the vertices is obtained while the edges connecting the vertices are added to the roadmap. Therefore, employing the vertex category classifier does not require much additional execution time. Secondly, the KSR path planner selects suitable developed strategies to prune the existing roadmap and add useful cycles according to the identified local environments where the vertices reside to improve the quality of the existing roadmap. Experimental results show that the KSR path planner can construct a roadmap and improve the quality of the roadmap incrementally while answering path queries until the roadmap can answer all the path queries without any pre-processing stage. The roadmap constructed by the KSR path planner then achieves better quality than the roadmaps constructed by Reconfigurable Random Forest (RRF) path planner and traditional probabilistic roadmap (PRM) path planner.

This thesis proposes new algorithms for a group of sensing robots to learn a para- metric model for a dynamic spatio-temporal field, then based on the learned model trajectories are planned for sensing robots to best estimate the field. In this thesis we call these two parts learning and monitoring, respectively. For the learning, we first introduce a parametric model for the spatio-temporal field. We then propose a family of motion strategies that can be used by a group of mobile sensing robots to collect point measurements about the field. Our motion strategies are designed to collect enough information from enough locations at enough different times for the robots to learn the dynamics of the field. In conjunction with these motion strategies, we propose a new learning algorithm based on subspace identification to learn the parameters of the dynamical model. We prove that as the number of data collected by the robots goes to infinity, the parameters learned by our algorithm will converge to the true parameters. For the monitoring, based on the model learned from the learning part, three new informative trajectory planning algorithms are proposed for the robots to collect the most informative measurements for estimating the field. Kalman filter is used to calculate the estimate, and to compute the error covariance of the estimate. The goal is to find trajectories for sensing robots that minimize a cost metric on the error covariance matrix. We propose three algorithms to deal with this problem. First, we propose a new randomized path planning algorithm called Rapidly-exploring Random Cycles (RRC) and its variant RRC* to find periodic trajectories for the sensing robots that try to minimize the largest eigenvalue of the error covariance matrix over an infinite horizon. The algorithm is proven to find the minimum infinite horizon cost cycle in a graph, which grows by successively adding random points. Secondly, we apply kinodynamic RRT* to plan continuous trajectories to estimate the field. We formulate the evolution of the estimation error covariance matrix as a differential constraint and propose extended state space and task space sampling to fit this problem into classical RRT* setup. Thirdly, Pontryagin’s Minimum Principle is used to find a set of necessary conditions that must be satisfied by the optimal trajectory to estimate the field. We then consider a real physical spatio-temporal field, the surface water temper- ature in the Caribbean Sea. We first apply the learning algorithm to learn a linear dynamical model for the temperature. Then based on the learned model, RRC and RRC* are used to plan trajectories to estimate the temperature. The estimation performance of RRC and RRC* trajectories significantly outperform the trajectories planned by random search, greedy and receding horizon algorithms.

Since their introduction in the 1950s, industrial Automated Guided Vehicles (AGV) have gone from automatic machinery limited by hardware to complex robots limited by software, called Autonomous Mobile Robots. Small and medium businesses need to be able to utilize cutting-edge technology. Therefore, this research focuses on deploying mapless AMRs on cheap open source AMRs in dynamic industrial environments. The study implements Dijkstra’s and A-STAR algorithms on a simulated Turtlebot3 model deployed in a Gazebo rendering of an industrial warehouse with moving objects added. The Turtlebot3 model traverses the environment where time and distance results are observed. The results shown in the research indicate that Dijkstra’s algorithm is barely affected by the change of the initial map state, while the A-STAR algorithm performed worse on average. Future work should focus on minimizing the sensors needed and continue testing with more algorithms, but early tests show promising results.

The present study proposes a novel approach to Coverage Path Planning for unmanned aerial vehicle (UAV) inspired by the Orienteering Problem. The main goal is to develop an algorithm suitable for Search and Rescue Missions, which can produce a search pattern with dynamical constrains, that is not limited to the traditional back-and-forth motion or spiral patterns. This method leads to a more flexible and diverse coverage of the Area of Interest. In order to generate dynamically correct trajectories, we utilize cubic splines as motion primitives to solve the Orienteering Problem. To accomplish this, we implement and test three different types of cubic splines, namely Catmull-Rom, Freya, and B-splines. To determine the coverage of the search area, the sensor's projection (footprint) is evaluated along the spline trajectory onto a costmap. This method accounts for the footprint's orientation and size, which depend on the UAV's attitude to some extent. This version of the Orienteering Problem using splines for dynamical control and calculating coverage, we call the Mapping Motion Orienteering Problem (MMOP). \\The heuristic method Simulated Annealing is used to address the combinatorial challenges of the MMOP, and two cost functions are tested for optimization. The study shows that the choice of spline has a significant impact on the algorithm's efficacy, and B-splines are the most effective in generating dynamic and adaptable trajectories. However, the study also shows that the Simulated Annealing algorithm with identical settings produced varied resulting paths. Finally, further research is needed to solve the challenges faced with the computational time, which heavily depends on factors such as the sampling rate for the footprint along the path and the resolution of the costmap and footprint itself.