The aim of the research project that is the subject of this thesis is to apply mathematical techniques, especially those in the area of operations research, to the problem of maritime minefield transit. We develop several minefield models applicable to different aspects of the minefield problem. These include optimal mine clearance, shortest time traversal and time constrained traversal. We hope the suite of models and tools developed will help make mine field clearance and traversal both safer and more efficient and that exposition of the models will bring a clearer understanding of the mine problem from a mathematical perspective. In developing the solutions to mine field models, extensive use is made of network path planning algorithms, particularly the Weight Constrained Shortest Path Problem (WCSPP) for which the current state-of-the-art algorithm is extended. This is done by closer integration of Lagrangean relaxation and preprocessing to reduce the size of the network. This is then integrated with gap-closing algorithms based on enumeration to provide optimal or near optimal solutions to the path planning problem. We provide extensive computational evidence on the performance of our algorithm and compare it to other algorithms found in the literature. This tool then became fundamental in solving various separate minefield models. Our models can be broadly separated into obstacle models in which mine affected regions are treated as obstacles to be avoided and continuous threat in which each point of space has an associated risk. In the later case, we wish to find a path that minimizes the integral of the risk along the path while constraining the length of the path. We call this the Continuous Euclidean Length Constrained Minimum Cost Path Problem (C-LCMCPP), for which we present a novel network approach to solving this continuous problem. This approach results in being able to calculate a global lower bound on a non-convex optimization problem.

Labor shortage has prompted researchers to develop robot platforms for agriculture field scouting tasks. Sensor-based automatic topographic mapping and scouting algorithms for rough and large unstructured environments were presented. It involves moving an image sensor to collect terrain and other information and concomitantly construct a terrain map in the working field. In this work, a triangular mesh map was first used to represent the rough field surface and plan exploring strategies. A 3D image sensor model was used to simulate collection of field elevation information.<p>A two-stage exploring policy was used to plan the next best viewpoint by considering both the distance and elevation change in the cost function. A greedy exploration algorithm based on the energy cost function was developed; the energy cost function not only considers the traveling distance, but also includes energy required to change elevation and the rolling resistance of the terrain. An information-based exploration policy was developed to choose the next best viewpoint to maximise the information gain and minimize the energy consumption. In a partially known environment, the information gain was estimated by applying the ray tracing algorithm. The two-part scouting algorithm was developed to address the field sampling problem; the coverage algorithm identifies a reasonable coverage path to traverse sampling points, while the dynamic path planning algorithm determines an optimal path between two adjacent sampling points.<p>The developed algorithms were validated in two agricultural fields and three virtual fields by simulation. Greedy exploration policy, based on energy consumption outperformed other pattern methods in energy, time, and travel distance in the first 80% of the exploration task. The exploration strategy, which incorporated the energy consumption and the information gain with a ray tracing algorithm using a coarse map, showed an advantage over other policies in terms of the total energy consumption and the path length by at least 6%. For scouting algorithms, line sweeping methods require less energy and a shorter distance than the potential function method.

In this thesis, energy optimal route of an unmanned solar powered air vehicle is obtained for the given mission constraints in order to sustain the maximum energy balance. The mission scenario and the constraints of the solar powered UAV are defined. Equations of motion are obtained for the UAV with respect to the chosen structural properties and aerodynamic parameters to achieve the given mission. Energy income and loss equations that state the energy balance, up to the position of the UAV inside the atmosphere are defined. The mathematical model and the cost function are defined according to the mission constraints, flight mechanics and energy balance equations to obtain the energy optimal path of the UAV. An available optimal control technique is chosen up to the mathematical model and the cost function in order to make the optimization. Energy optimal path of the UAV is presented with the other useful results. Optimal route and the other results are criticized by checking them with the critical positions of the sun rays.

Over the past few years, manufacturing companies have had to deal with an increasing demand for feature-rich products at low costs. The pressures exerted on their existing manufacturing processes have lead manufacturers to investigate internet-based solutions, in order to cope with growing competition. Today, the availability of powerful and low cost 3D tools, along with web-based technologies, provides interesting opportunities to the manufacturing community, with solutions directly implementable at the core of their businesses and organizations. The wooden sign is custom i.e. each sign is completely different from each other. Mass Customization is a paradigm that produces custom products in masses. A wooden sign is custom in nature, and each sign must be completely different from another. Although process planning for mass customized products is same, the tool path required to CNC machine the custom feature varies from part to part. If the tool path is created manually the economics of mass production are challenged. The only viable option is to generate the tool path automatically; furthermore, any time savings in the tool path lead to better profit margins. This thesis presents the automatic web-based tool path planning method for machining sculptured wooden sign on 3 axis Computer Numerical Controlling (CNC) Machines using optimal and cost-effective milling cutters. The web-based tool path planning strategy is integrate with web-based CAD system to automatically generate tool paths for the CAD model using optimal cutter within desired tolerances. The tool path planning method is divided into two parts: foot print (path along which cutter moves) and cutter positioning. The tool path foot print is developed during design stage from the CAD model based on the type of surface to be machined. The foot print varies from part to part which facilitates the mass customization of wooden sign. After designing foot print, the foot print is discretized into points and the gouge-free cutter position at each of these points is found using "Dropping Method". The Dropping Method where cutter is dropped over the work piece surface, and the highest depth at which cutter can go without gouging the surface is calculated. This is repeated for all the position along the foot print. This tool path planning strategy is developed for ball nose, flat-end and radiused end milling cutter for machining wooden sign. The tool path generated using this method is optimized for machining time, tool path generation time and final surface finish. The bucketing technique is developed to optimize tool path generation time, by isolating the triangles which has possibility of intersection at particular position. The bucketing Technique reduced the tool path computation by 75 %, and made tool path generation faster. The optimal cutter selection algorithm is developed which selects best cutter for machining the surface based on the scallop height and volume removal results. The radiused end milling cutter results in highest volume removal which results in lower machining time compared to ball nose end milling cutters, but the scallop heights is higher. However, the scallop height in the radiused end milling cutter is higher only in few regions which reduces the final surface finish. For a sign, it was found around the boundary of logo, outline of lettering, interface of border and background. Thus, in order to achieve higher surface finish and lower machining time, a separate tool path is developed using "Pencil Milling Technique" which will remove the scallops from the regions that was inaccessible by radiused end mills. This tool path with the smaller cutter will move around the boundary of logo and lettering, and clean-up all the scallops left on the surface. The designed tool path for all the three cutters were tested on maple wood and verified against the actual Computer Aided Design model for scallop height and surface finish. The numerical testing of tool path was carried out on a Custom Simulator, ToolSim and was later confirmed by actually machining on a 3 axis CNC machine. The same sign was machined with variety of milling cutters and the best cutter was selected based on the minimum scallop and maximum volume removal. The results of the experimental verification show the method to be accurate for machining sculptured sign. The average scallop height in a machined using 1/8 th inch radiused end milling cuter and using Pencil tool path on the machined surface is found to be 0.03989 mm (1.5708 thou).

A unique mathematical tool is developed to deal with global optimization of a set of engineering problems. These include image processing, mechanical topology optimization, and optimal path planning in a variational framework, as well as some benchmark problems in parameter optimization. The optimization tool in these applications is based on the level set theory by which an evolving contour converges toward the optimum solution. Depending upon the application, the objective function is defined, and then the level set theory is used for optimization. Level set theory, as a member of active contour methods, is an extension of the steepest descent method in conventional parameter optimization to the variational framework. It intrinsically suffers from trapping in local solutions, a common drawback of gradient based optimization methods. In this thesis, methods are developed to deal with this drawbacks of the level set approach. By investigating the current global optimization methods, one can conclude that these methods usually cannot be extended to the variational framework; or if they can, the computational costs become drastically expensive. To cope with this complexity, a global optimization algorithm is first developed in parameter space and compared with the existing methods. This method is called "Spiral Bacterial Foraging Optimization" (SBFO) method because it is inspired by the aggregation process of a particular bacterium called, Dictyostelium Discoideum. Regardless of the real phenomenon behind the SBFO, it leads to new ideas in developing global optimization methods. According to these ideas, an effective global optimization method should have i) a stochastic operator, and/or ii) a multi-agent structure. These two properties are very common in the existing global optimization methods. To improve the computational time and costs, the algorithm may include gradient-based approaches to increase the convergence speed. This property is particularly available in SBFO and it is the basis on which SBFO can be extended to variational framework. To mitigate the computational costs of the algorithm, use of the gradient based approaches can be helpful. Therefore, SBFO as a multi-agent stochastic gradient based structure can be extended to multi-agent stochastic level set method. In three steps, the variational set up is formulated: i) A single stochastic level set method, called "Active Contours with Stochastic Fronts" (ACSF), ii) Multi-agent stochastic level set method (MSLSM), and iii) Stochastic level set method without gradient such as E-ARC algorithm. For image processing applications, the first two steps have been implemented and show significant improvement in the results. As expected, a multi agent structure is more accurate in terms of ability to find the global solution but it is much more computationally expensive. According to the results, if one uses an initial level set with enough holes in its topology, a single stochastic level set method can achieve almost the same level of accuracy as a multi-agent structure can obtain. Therefore, for a topology optimization problem for which a high level of calculations (at each iteration a finite element model should be solved) is required, only ACSF with initial guess with multiple holes is implemented. In some applications, such as optimal path planning, objective functions are usually very complicated; finding a closed-form equation for the objective function and its gradient is therefore impossible or sometimes very computationally expensive. In these situations, the level set theory and its extensions cannot be directly employed. As a result, the Evolving Arc algorithm that is inspired by "Electric Arc" in nature, is proposed. The results show that it can be a good solution for either unconstrained or constrained problems. Finally, a rigorous convergence analysis for SBFO and ACSF is presented that is new amongst global optimization methods in both parameter and variational framework.

Labor shortage has prompted researchers to develop robot platforms for agriculture field scouting tasks. Sensor-based automatic topographic mapping and scouting algorithms for rough and large unstructured environments were presented. It involves moving an image sensor to collect terrain and other information and concomitantly construct a terrain map in the working field. In this work, a triangular mesh map was first used to represent the rough field surface and plan exploring strategies. A 3D image sensor model was used to simulate collection of field elevation information.<p>A two-stage exploring policy was used to plan the next best viewpoint by considering both the distance and elevation change in the cost function. A greedy exploration algorithm based on the energy cost function was developed; the energy cost function not only considers the traveling distance, but also includes energy required to change elevation and the rolling resistance of the terrain. An information-based exploration policy was developed to choose the next best viewpoint to maximise the information gain and minimize the energy consumption. In a partially known environment, the information gain was estimated by applying the ray tracing algorithm. The two-part scouting algorithm was developed to address the field sampling problem; the coverage algorithm identifies a reasonable coverage path to traverse sampling points, while the dynamic path planning algorithm determines an optimal path between two adjacent sampling points.<p>The developed algorithms were validated in two agricultural fields and three virtual fields by simulation. Greedy exploration policy, based on energy consumption outperformed other pattern methods in energy, time, and travel distance in the first 80% of the exploration task. The exploration strategy, which incorporated the energy consumption and the information gain with a ray tracing algorithm using a coarse map, showed an advantage over other policies in terms of the total energy consumption and the path length by at least 6%. For scouting algorithms, line sweeping methods require less energy and a shorter distance than the potential function method.

Recently there has been a tremendous growth of research emphasizing control of unmanned aerial vehicles (UAVs) either in isolation or in teams. As a matter of fact, UAVs increasingly find their way to applications, especially in military and law enforcement (e.g., reconnaissance, remote delivery of urgent equipment/material, resource assessment, environmental monitoring, battlefield monitoring, ordnance delivery, etc.). This trend will continue in the future, as UAVs are poised to replace the human-in-the-loop during dangerous missions. Civilian applications of UAVs are also envisioned such as crop dusting, geological surveying, search and rescue operations, etc. In this thesis we propose a new online multiresolution path planning algorithm for a small UAV with limited on-board computational resources. The proposed approach assumes that the UAV has detailed information of the environment and the obstacles only in its vicinity. Information about far-away obstacles is also available, albeit less accurately. The proposed algorithm uses the fast lifting wavelet transform (FLWT) to get a multiresolution cell decomposition of the environment, whose dimension is commensurate to the on-board computational resources. A topological graph representation of the multiresolution cell decomposition is constructed efficiently, directly from the approximation and detail wavelet coefficients. Dynamic path planning is sequentially executed for an optimal path using the A* algorithm over the resulting graph. The proposed path planning algorithm is implemented on-line on a small autopilot. Comparisons with the standard D*-lite algorithm are also presented. We also investigate the problem of generating a smooth, planar reference path from a discrete optimal path. Upon the optimal path being represented as a sequence of cells in square geometry, we derive a smooth B-spline path that is constrained inside a channel that is induced by the geometry of the cells. To this end, a constrained optimization problem is formulated by setting up geometric linear constraints as well as boundary conditions. Subsequently, we construct B-spline path templates by solving a set of distinct optimization problems. For an application to the UAV motion planning, the path templates are incorporated to replace parts of the entire path by the smooth B-spline paths. Each path segment is stitched together while preserving continuity to obtain a final smooth reference path to be used for path following control. The path following control for a small fixed-wing UAV to track the prescribed smooth reference path is also addressed. Assuming the UAV is equipped with an autopilot for low level control, we adopt a kinematic error model with respect to the moving Serret-Frenet frame attached to a path for tracking controller design. A kinematic path following control law that commands heading rate is presented. Backstepping is applied to derive the roll angle command by taking into account the approximate closed-loop roll dynamics. A parameter adaptation technique is employed to account for the inaccurate time constant of the closed-loop roll dynamics during actual implementation. Finally, we implement the proposed hierarchical path control of a small UAV on the actual hardware platform, which is based on an 1/5 scale R/C model airframe (Decathlon) and the autopilot hardware and software. Based on the hardware-in-the-loop (HIL) simulation environment, the proposed hierarchical path control algorithm has been validated through the on-line, real-time implementation on a small micro-controller. By a seamless integration of the control algorithms for path planning, path smoothing, and path following, it has been demonstrated that the UAV equipped with a small autopilot having limited computational resources manages to accomplish the path control objective to reach the goal while avoiding obstacles with minimal human intervention.

In this dissertation, the problem of planning the motion of m Unmanned Vehicles (UVs) (or simply vehicles) through n points in a plane is considered. A motion plan for a vehicle is given by the sequence of points and the corresponding angles at which each point must be visited by the vehicle. We require that each vehicle return to the same initial location(depot) at the same heading after visiting the points. The objective of the motion planning problem is to choose at most q(≤ m) UVs and find their motion plans so that all the points are visited and the total cost of the tours of the chosen vehicles is a minimum amongst all the possible choices of vehicles and their tours. This problem is a generalization of the wellknown Traveling Salesman Problem (TSP) in many ways: (1) each UV takes the role of salesman (2) motion constraints of the UVs play an important role in determining the cost of travel between any two locations; in fact, the cost of the travel between any two locations depends on direction of travel along with the heading at the origin and destination, and (3) there is an additional combinatorial complexity stemming from the need to partition the points to be visited by each UV and the set of UVs that must be employed by the mission. In this dissertation, a sub-optimal, two-step approach to motion planning is presented to solve this problem:(1) the combinatorial problem of choosing the vehicles and their associated tours is based on Euclidean distances between points and (2) once the sequence of points to be visited is specified, the heading at each point is determined based on a Dynamic Programming scheme. The solution to the first step is based on a generalization of Held-Karp’s method. We modify the Lagrangian heuristics for finding a close sub-optimal solution. In the later chapters of the dissertation, we relax the assumption that all vehicles are homogenous. The motivation of heterogenous variant of Multi-depot, Multiple Traveling Salesmen Problem (MDMTSP) derives form applications involving Unmanned Aerial Vehicles (UAVs) or ground robots requiring multiple vehicles with different capabilities to visit a set of locations.

Rapid prototyping (RP) is a set of fabrication technologies that are used to produce accurate parts directly from computer aided drawing (CAD) data. These technologies are unique in a way that they use an additive fabrication approach in which a three dimensional (3D) object is directly produced. In this thesis study, a RP application with a modular architecture is designed and implemented to satisfy the possible requirements of future rapid prototyping studies. After a functional classification, the developed RP software is divided into View, RP and Slice Modules. In the RP module, the process parameter selection and optimal build orientation determination steps are carried out. In the Slice Module, slicing and tool path generation steps are performed. View Module is used to visualize the inputs and outputs of the RP software. To provide 3D visualization support for View Module, a fully independent, open for development, high level 3D modeling environment and graphics library called Graphics Framework is developed. The resulting RP application is benchmarked with the RP software packages in the market according to their memory usage and process time. As a result of this benchmark, it is observed that the developed RP software has presented an equivalent performance with the other commercial RP applications and has proved its success.

Autonomous mobile robots - both aerial and terrestrial vehicles - have gained immense importance due to the broad spectrum of their potential military and civilian applications. One of the indispensable requirements for the autonomy of a mobile vehicle is the vehicle's capability of planning and executing its motion, that is, finding appropriate control inputs for the vehicle such that the resulting vehicle motion satisfies the requirements of the vehicular task. The motion planning and control problem is inherently complex because it involves two disparate sub-problems: (1) satisfaction of the vehicular task requirements, which requires tools from combinatorics and/or formal methods, and (2) design of the vehicle control laws, which requires tools from dynamical systems and control theory. Accordingly, this problem is usually decomposed and solved over two levels of hierarchy. The higher level, called the geometric path planning level, finds a geometric path that satisfies the vehicular task requirements, e.g., obstacle avoidance. The lower level, called the trajectory planning level, involves sufficient smoothening of this geometric path followed by a suitable time parametrization to obtain a reference trajectory for the vehicle. Although simple and efficient, such hierarchical separation suffers a serious drawback: the geometric path planner has no information of the kinematic and dynamic constraints of the vehicle. Consequently, the geometric planner may produce paths that the trajectory planner cannot transform into a feasible reference trajectory. Two main ideas appear in the literature to remedy this problem: (a) randomized sampling-based planning, which eliminates altogether the geometric planner by planning in the vehicle state space, and (b) geometric planning supported by feedback control laws. The former class of methods suffer from a lack of optimality of the resultant trajectory, while the latter class of methods makes a restrictive assumption concerning the vehicle kinematic model. In this thesis, we propose a hierarchical motion planning framework based on a novel mode of interaction between these two levels of planning. This interaction rests on the solution of a special shortest-path problem on graphs, namely, one using costs defined on multiple edge transitions in the path instead of the usual single edge transition costs. These costs are provided by a local trajectory generation algorithm, which we implement using model predictive control and the concept of effective target sets for simplifying the non-convex constraints involved in the problem. The proposed motion planner ensures "consistency" between the two levels of planning, i.e., a guarantee that the higher level geometric path is always associated with a kinematically and dynamically feasible trajectory. We show that the proposed motion planning approach offers distinct advantages in comparison with the competing approaches of discretization of the state space, of randomized sampling-based motion planning, and of local feedback-based, decoupled hierarchical motion planning. Finally, we propose a multi-resolution implementation of the proposed motion planner, which requires accurate descriptions of the environment and the vehicle only for short-term, local motion planning in the immediate vicinity of the vehicle.