abstract: With robots being used extensively in various areas, a certain degree of robot autonomy has always been found desirable. In applications like planetary exploration, autonomous path planning and navigation are considered essential. But every now and then, a need to modify the robot's operation arises, a need for a human to provide it some supervisory parameters that modify the degree of autonomy or allocate extra tasks to the robot. In this regard, this thesis presents an approach to include a provision to accept and incorporate such human inputs and modify the navigation functions of the robot accordingly. Concepts such as applying kinematical constraints while planning paths, traversing of unknown areas with an intent of maximizing field of view, performing complex tasks on command etc. have been examined and implemented. The approaches have been tested in Robot Operating System (ROS), using robots such as the iRobot Create, Personal Robotics (PR2) etc. Simulations and experimental demonstrations have proved that this approach is feasible for solving some of the existing problems and that it certainly can pave way to further research for enhancing functionality. / Dissertation/Thesis / M.S. Electrical Engineering 2013

No description available.

As a result of recent technological advances in modernized sensor sets and sensor platforms, sensor management combined with sensor platform path planning are studied to conduct intelligence, surveillance and reconnaissance (ISR) operations in novel ways. This thesis addresses the path planning and sensor management for aerial vehicles to cover areas of interest (AOIs), scan objects of interest (OOIs) and/or track multiple detected targets in surveillance missions. The problems in this thesis, which include 1) the spatio-temporal coordination of sensor platforms to observe AOIs or OOIs, 2) the optimal sensor geometry and path planning for localization and tracking of targets in a mobile three-dimensional (3D) space, and 3) the scheduling of sensors working in different (i.e., active and passive) modes combined with path planning to track targets in the presence of jammers, emerge from real-world demands and scenarios. The platform path planning combined with sensor management is formulated as optimization problems with problem-dependent performance evaluation metrics and constraints. Firstly, to cover disjoint AOIs over an extended time horizon using multiple aerial vehicles for persistent surveillance, a joint multi-period coverage path planning and temporal scheduling, which allows revisiting in a single-period path, is formulated as a combinatorial optimization with novel objective functions. Secondly, to use a group of unmanned aerial vehicles (UAVs) cooperatively carrying out search-and-track (SAT) in a mobile 3D space with a number of targets, a joint path planning and scanning (JPPS) is formulated based on the predictive information gathered from the search space. The optimal 3D sensor geometry for target localization is also analyzed with the objective to minimize the estimation uncertainty under constraints on sensor altitude, sensor-to-sensor and sensor-to-target distances for active or passive sensors. At last, to accurately track targets in the presence of jammers broadcasting wide-band noise by taking advantage of the platform path planning and the jammer's information captured by passive sensors, a joint path planning and active-passive scheduling (JPPAPS) strategy is developed based on the predicted tracking performance at the future time steps in a 3D contested environment. The constraints on platform kinematic, flyable area and sensing capacity are included in these optimization problems. For these multisensor path planning and decision making, solution techniques based on the genetic algorithm are developed with specific chromosome representations and custom genetic operators using either the non-dominated sorting multiobjective optimization (MOO) architecture or the weighted-sum MOO architecture. Simulation results illustrate the performance and advantage of the proposed strategies and methods in real-world surveillance scenarios. / Thesis / Doctor of Philosophy (PhD)

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.

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.

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.