This work presents a new class of algorithms that extend the domain of Navigation Among Movable Obstacles (NAMO) to unknown environments. Efficient real-time algorithms for solving NAMO problems even when no initial environment information is available to the robot are presented and validated. The algorithms yield optimal solutions and are evaluated for real-time performance on a series of simulated domains with more than 70 obstacles. In contrast to previous NAMO algorithms that required a pre-specified environment model, this work considers the realistic domain where the robot is limited by its sensor range. It must navigate to a goal position in an environment of static and movable objects. The robot can move objects if the goal cannot be reached or if moving the object significantly shortens the path. The robot gains information about the world by bringing distant objects into its sensor range. The first practical planner for this exponentially complex domain is presented. The planner reduces the search-space through a collection of techniques, such as upper bound calculations and the maintenance of sorted lists with underestimates. Further, the algorithm is only considering manipulation actions if these actions are creating a new opening in the environment. In the addition to the evaluation of the planner itself is each of this techniques also validated independently.

The purpose of this thesis is to develop a testing environment for mobile robot experiments, to examine methods for multi-robot platooning through hostile environments, and test these algorithms on mobile robots. Such a system will allow us to rapidly address and test problems that arise concerning robot swarms and consequent interactions. In order to create this hardware simulation environment a test bed will be created using ROS or Robot Operating System. This platform is highly modular and extensible for future development. Trajectory generation for the robots will use smoothing splines, B-splines, and A* search. Each method has distinct properties which will be analyzed and rated with respect to its effectiveness with regards to robotic platooning. A few issues to be considered include: Is the optimal path taken with respect to distance and threats? Is the formation of the robots maintained or compromised during traversal of the path? And finally, what sorts of compromises or additions are needed to make each method effective? This work will be helpful for choosing route planning methods in future work and will provide a large code base for rapid prototyping.

Mobile robots are gaining increased autonomy due to advances in sensor and computing technology. In their current form however, robots still lack algorithms for rapid perception of objects in a cluttered environment and can benefit from the assistance of a human operator. Further, fully autonomous systems will continue to be computationally expensive and costly for quite some time. Humans can visually assess objects and determine whether a certain path is traversable, but need not be involved in the low-level steering around any detected obstacles as is necessary in remote-controlled systems. If only used for rapid perception tasks, the operator could potentially assist several mobile robots performing various tasks such as exploration, surveillance, industrial work and search and rescue operations. There is a need to develop better human-robot interaction paradigms that would allow the human operator to effectively control and manage one or more mobile robots. This paper proposes a method of enhancing user effectiveness in controlling multiple mobile robots through real-time map manipulation. An interface is created that would allow a human operator to add virtual obstacles to the map that represents areas that the robot should avoid. A video camera is connected to the robot that would allow a human user to view the robot's environment. The combination of real-time map editing and live video streaming enables the robot to take advantage of human vision, which is still more effective at general object identification than current computer vision technology. Experimental results show that the robot is able to plan a faster path around an obstacle when the user marks the obstacle on the map, as opposed to allowing the robot to navigate on its own around an unmapped obstacle. Tests conducted on multiple users suggest that the accuracy in placing obstacles on the map decreases with increasing distance of the viewing apparatus from the obstacle. Despite this, the user can take advantage of landmarks found in the video and in the map in order to determine an obstacle's position on the map.

The present investigation focuses on the development of computationally efficient path planning algorithms for autonomous ground vehicles. The approach selected is based on a heuristic hill climbing local search. The cost index employed incorporates a traversability cost average, which offers two primary benefits: 1) the average extends the region of knowledge of the search algorithm, increasing optimality of the solution; and 2) the avoidance of hazardous regions is added to the decision making process. A binary traversability map representation is first utilized to analyze the performance of the enhanced heuristic hill climbing algorithm in comparison to the more traditional techniques. Next, the search algorithm is applied to a multi-valued traversability map to test the capabilities of the algorithm over natural terrain. For this purpose, a digital elevation map is automatically processed to obtain multi-valued traversability values through the de nition of a roughness, inclination and step index. The complete path planning architecture for natural terrain then consists of a three step approach, computation of the multi-valued traversability map, implementation of the enhanced heuristic hill climbing search algorithm, and a path relaxation step. This last step is employed to fine-tune and smooth the trajectory, eliminating sharp turns caused by the regular characteristics of the search space. / text

The ultimate goal in robotics is to create machines which are more independent and rely less on humans to guide them in their operation. There are many sub-systems which may be present in such a robot, one of which is path planning — the ability to determine a sequence of positions or configurations between an initial and goal position within a particular obstacle cluttered workspace. Many classical path planning techniques have been developed, but these tend to have drawbacks such as their computational requirements; the suitability of the plans they produce for a particular application; or how well they are able to generalise to unseen problems. In recent years, evolutionary based problem solving techniques have seen a rise in popularity, possibly coinciding with the improvement in the computational power afforded researches by successful developments in hardware. These techniques adopt some of the features of natural evolution and mimic them in a computer. The increase in the number of publications in the areas of Genetic Algorithms (GA) and Genetic Programming (GP) demonstrate the success achieved when applying these techniques to ever more problem areas. This dissertation presents research conducted to determine whether there is a place for Evolutionary Approaches, and specifically GA and GP, in the development of future path planning techniques.

Motion planning is an increasingly important field of research. Factory automation is becoming more prevalent and at the same time, production runs are shortening in the name of customisation. With computer controlled equipment becoming cheaper and more modular, setting up near-fully automated production lines is becoming fast and easy. This means that the actual programming of the robots and assembly system is becoming the rate determining step. Automated motion planning is a possible solution to this—but only if it can run fast enough. Many heuristic planners have been created in an attempt to achieve the necessary speeds in off-line (or more ambitiously, on-line) processing. This thesis aims to show that different types of heuristic planners can be designed to take advantage of specialised environments or robot characteristics. To show this, three distinct classes of heuristic planners are put forward for discussion. The first of these classes, addressed in Chapter 2, is of very generic planners which will work in virtually all situations (ie. almost any combination of robot and environment). This generality is obviously useful when lacking more specific domain knowledge. However these methods do suffer performance-wise in comparison with more specialised planners when there are characteristics of the problem which can be targeted. Chapter 3 moves to planners which are designed to specifically address certain peculiarities of the environment. Particular focus is given to environments whose corresponding configuration-spaces contain narrow gaps and passages. Finally Chapter 4 addresses a third class of planners: those which are designed for specific types of robots and movements. The particular focus is on locomotion for legged vehicles. For each of these three classes, some discussion is made of existing planners which can be so characterised. In addition, a novel algorithm is introduced in each as an example for particular consideration.

Path planning and image processing are critical signal processing tasks for robots, autonomous vehicles, animated characters, etc. The ultimate goal of the path planning problem being addressed in this dissertation is how to use a reconfigurable Analog Very Large Scale Integration (AVLSI) circuit to plan a path for a Micro Aerial Vehicle (MAV) (or similar power constrained ground or sea robot) through an environment in an effort to conserve its limited battery resources. Path planning can be summarized with the following three tasks given that states, actions, an initial state, and a goal state are provided. The robot should: 1) Find a sequence of actions that take the robot from its Initial state to its Goal state. 2) Find actions that take the robot from any state to the Goal state, and 3) Decide the best action for the robot to take now in order to improve its odds of reaching the Goal. Image processing techniques can be used to visually track an object. Segmenting the object from the background is one subtask in this problem. Digital image processing can be very computationally expensive in terms of memory and data manipulation. Path planning and image processing computations are typically executed on digital microprocessors. This dissertation explores an evolution of analog signal processing using Field Programmable Analog Arrays (FPAAs); it describes techniques for mapping different solutions onto the hardware, and it describes the benefits and limitations. The motivation is lower power, more capable solutions that also provide better algorithm performance metrics such as time and space complexity. This may be a significant advantage for MAVs, ocean gliders or other robot applications where the power budget for on-board signal processing is limited.

This thesis consists of two parts united by the theme of path/action planning for a mobile robot. Part I presents the Second Opinion Planner (SOP), and Part II presents a new paradigm for navigating, growing, and planning on a Network of Reusable Paths (NRP). Path/action planning is common to both parts in that the planning algorithm must choose the terrain assessment or localization technique at the path-planning stage. Terrain-assessment algorithms follow the trend of low-fidelity at low-cost and high-fidelity at high-cost. Using a high-fidelity method on all the raw terrain data can drastically increase a robot's total path cost (cost of driving, planning, and doing the terrain assessment). SOP is a path-planning algorithm that uses a hierarchy of terrain-assessment methods, from low-fidelity to high-fidelity, and seeks to limit high-cost assessment to areas where it is beneficial. The decision to assess some terrain with a higher-fidelity method is made considering potential path benefits and the cost of assessment. SOP provides a means to triage large amounts of terrain data. The system is demonstrated on simulated problems and in real terrain from an experimental field test carried out on Devon Island, Canada. The SOP plans are quite close to the minimum possible cost. Growing a NRP is an approach to navigation that allows a mobile robot to autonomously explore unmapped, GPS-denied environments. This new paradigm results in closer goal acquisition and a more robust approach to exploration with a mobile robot, when compared to a classic approach to guidance, navigation, and control. A NRP is a simple Simultaneous Localization And Mapping system that can be shown to be a physical embodiment of a Rapidly-exploring Random Tree planner. Simulation results are presented, as well as the results from two different robotic test systems that were tested in planetary analogue environments. NRP offers benefits to planetary exploration by allowing a rover to be used for the parallel scientific investigations. This increases the number of sites that can be investigated in a short time, as compared to a serial approach to exploration. Two mock missions were carried out at planetary analogue sites.

This thesis consists of two parts united by the theme of path/action planning for a mobile robot. Part I presents the Second Opinion Planner (SOP), and Part II presents a new paradigm for navigating, growing, and planning on a Network of Reusable Paths (NRP). Path/action planning is common to both parts in that the planning algorithm must choose the terrain assessment or localization technique at the path-planning stage. Terrain-assessment algorithms follow the trend of low-fidelity at low-cost and high-fidelity at high-cost. Using a high-fidelity method on all the raw terrain data can drastically increase a robot's total path cost (cost of driving, planning, and doing the terrain assessment). SOP is a path-planning algorithm that uses a hierarchy of terrain-assessment methods, from low-fidelity to high-fidelity, and seeks to limit high-cost assessment to areas where it is beneficial. The decision to assess some terrain with a higher-fidelity method is made considering potential path benefits and the cost of assessment. SOP provides a means to triage large amounts of terrain data. The system is demonstrated on simulated problems and in real terrain from an experimental field test carried out on Devon Island, Canada. The SOP plans are quite close to the minimum possible cost. Growing a NRP is an approach to navigation that allows a mobile robot to autonomously explore unmapped, GPS-denied environments. This new paradigm results in closer goal acquisition and a more robust approach to exploration with a mobile robot, when compared to a classic approach to guidance, navigation, and control. A NRP is a simple Simultaneous Localization And Mapping system that can be shown to be a physical embodiment of a Rapidly-exploring Random Tree planner. Simulation results are presented, as well as the results from two different robotic test systems that were tested in planetary analogue environments. NRP offers benefits to planetary exploration by allowing a rover to be used for the parallel scientific investigations. This increases the number of sites that can be investigated in a short time, as compared to a serial approach to exploration. Two mock missions were carried out at planetary analogue sites.

The purpose of this work is to provide simulation-based support for making optimal (or near-optimal) decisions in situations where decision makers are faced with imperfect information. We develop several novel techniques and algorithms for simulation-based optimization and decision support and apply them to two categories of problems: (i) Unmanned Aerial Vehicle (UAV) path planning in search operations, and; (ii) optimization of business process models. Common features of these two problems for which analytical approaches are not available, are the presence of imperfect information and their inherent complexity. In the UAV path planning problem, the objective is to define the path of a UAV searching for a target on a known road network. It is assumed that the target is moving toward a goal and we have some uncertain information about the start point of the target, its velocity, and the final goal of the target. The target does not take evasive action to avoid being detected. The UAV is equipped with a sensor, which may detect the target once it is in the sensor’s scope. Nevertheless, the detection process is uncertain and the sensor is subject to both false-positive and false-negative errors. We propose three different solutions, two of which are simulation-based. The most promising solution is an on-line simulation-based method that estimates the location of the target by using a Sequential Monte Carlo (SMC) method. During the entire mission, different UAV paths are simulated and the one is chosen that most reduces the uncertainty about the location of the target. In the optimization of the business process models, several different but related problems are addressed: (i) we define a measure of performance for a business process model based on the value added by agents (employees) to the process; (ii) we use this model for optimization of the business process models. Different types of processes are distinguished and methods for finding the optimal or near-optimal solutions are provided; (iii) we propose a model for estimating the performance of collaborative agents. This model is used to solve a class of Assignment Problems (AP), where tasks are assigned to collaborative agents; (iv) we propose a model for team activity and the performance of a team of agents. We introduce different collaboration strategies between agents and a negotiation algorithm for resolving conflicts between agents. We compare the effect of different strategies on the output of the team. Most of the studied cases are complex problems for which no analytical solution is available. Simulation methods are successfully applied to these problems. They are shown to be more general than analytical models for handling uncertainty since they usually have fewer assumptions and impose no restrictions on the probability distributions involved. Our investigation confirms that simulation is a powerful tool for providing decision-making support. Moreover, our proposed algorithms and methods in the accompanying articles contribute to providing support for making optimal and in some cases near-optimal decisions: (i) our tests of the UAV simulation-based search methods on a simulator show that the on-line simulation method has generally a high performance and detects the target in a reasonable time. The performance of this method was compared with the detection time when the UAV had the exact information about the initial location of the target, its velocity, and its path (minimum detection time). This comparison indicated that the online simulation method in many cases achieved a near-optimal performance in the studied scenario; (ii) our business process optimization framework combines simulation with the Hungarian method and finds the optimal solution for all cases where the assignment of tasks does not change the workflow of the process. For the most general cases, where the assignment of tasks may change the workflow, we propose an algorithm that finds near-optimal solutions. In this algorithm, simulation, which deals with the uncertainty in the process, is combined with the Hungarian method and hill-climbing heuristics. In the study of assigning tasks to collaborative agents we suggest a Genetic Algorithm (GA) that finds near-optimal solutions with a high degree of accuracy, stability, scalability and robustness. While investigating the effect of different agent strategies on the output of a team, we find that the output of a team is near-optimal, when agents choose a collaboration strategy that follows the principle of least effort (Zipf’s law) and use our suggested algorithm for negotiation and resolving conflicts. / QC 20111202