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.

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.

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).

Approved for public release; distribution is unlimited / Unmanned vehicle technology has matured significantly over the last two decades. This is evidenced by its widespread use in industrial and military applications ranging from deep-ocean exploration to anti-submarine warefare. Indeed, the feasiblity of short-range, special-purpose vehicles (whether aunonomous or remotely operated) is no longer in question. The research efforts have now begun to shift their focus on development of reliable, longer-range, high-endurance and fully autonomous systems. One of the major underlying technologies required to realize this goal is Artificial Intelligence (AI). The latter offers great potential to endow vehicles with the intelligence needed for full autonomy and extended range capability; this involves the increased application of AI technologies to support mission planning and execution, navigation and contingency planning. This thesis addresses two issues associated with the above goal for Autonomous Underwater Vehicles (AUV's). Firstly, a new approach is proposed for path planning in underwater environments that is capable of dealing with uncharted obstacles and which requires significantly less planning time and computer memory. Secondly, it explores the use of expert system technology in the planning of AUV missions.

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.

Motion planning is central to the efficient operation and autonomy of robots in the industry. Generally, motion planning of industrial robots is treated in a two-step approach. First, a geometric path between the start and goal position is planned where the objective is to achieve as short path as possible together with avoiding obstacles. Alternatively, a pre-defined geometric path is provided by the end user. Second, the velocity profile along the geometric path is calculated accounting for system dynamics together with other constraints. This approach is computationally efficient, but yield sub-optimal solutions as the system dynamics is not considered in the first step when the geometric path is planned. In this thesis, an alternative to the two-step approach is investigated and a trajectory planner is designed and implemented which plans both the geometric path and the velocity profile simultaneously. The motion planning problem is formulated as an optimal control problem, which is solved by a direct collocation method where the trajectory is parametrised by splines, and the spline nodes and knots are used as optimization variables. The implemented trajectory planner is evaluated in simulations, where the planner is applied to a simple planar elbow robot and ABB's SCARA robot IRB 910SC. Trade-off between computation time and optimality is identified and the results indicate that the trajectory planner yields satisfactory solutions. On the other hand, the simulations indicate that it is not possible to apply the proposed method on a real robot in real-time applications without significant modifications in the implementation to decrease the computation time.

This thesis is concerned with the robots' motion planning problem. In particular it is focused on the path planning and motion planning for Autonomously Guided Vehicles (AGVs) in well-structured, two-dimensional static and dynamic environments. Two algorithms are proposed for solving the aforementioned problems. The first algorithm establishes the shortest collision-semi-free path for an AGV from its start point to its goal point, in a two-dimensional static environment populated by simple polygonal obstacles. This algorithm constructs and searches a reduced visibility graph, within the AGV's configuration space, using heuristic information about the problem domain. The second algorithm establishes the time minimal collision-semi-free motion for an AGV, from its start point to is goal point, in a two-dimensional dynamic environment populated by simple polygonal obstacles. This algorithm considers the AGV's spacetime configuration space, thus reducing the dynamic motion planning problem to the static path planning problem. A reduced visibility graph is then constructed and searched using information about the problem domain, in the AGV's space-time configuration space in order to establish the time-minimal motion between the AGV's start and goal configurations. The latter algorithm is extended to solve more complicated instances of the dynamic motion planning problem, where the AGV's environment is populated by obstacles, which change their size as well as their position over time and obstacles, which have piecewise linear motion. The proposed algorithms can be used to efficiently and safely navigate AGVs in well structured environments. For example, for the navigation of an AGV, in industrial environments, where it operates as part of the manufacturing process or in chemical and nuclear plants, where the hostile environment is inaccessible to humans. The main contributions in this thesis are, the systematic study of the V*GRAPH algorithm and identification of its methodic and algorithmic deficiencies; recommendation of corrections and further improvements on the V* GRAPH algorithm, which in turn lead to the proposition of the V*MECHA algorithm for robot path planning; proposition of the D*MECHA algorithm for motion planning in dynamic environments; extension to the D*MECHA algorithm to solve more complicated instances of the dynamic robot motion planning problem; discussion of formal proofs of the proposed algorithms' correctness and optimality and critical comparisons with existing similar algorithms for solving the motion planning problem.

presente trabalho consolida um estudo para o planejamento de trajetória livre de colisão para um robô pneumático com 5 graus de liberdade aplicando três algoritmos metaheurísticos: algoritmos metaheurísticos por vagalumes, algoritmos metaheurísticos por enxames de partículas e algoritmos genéticos. No que se refere à aplicação de algoritmos metaheurísticos ao estudo de planejamento de trajetória de robôs manipuladores na presença de obstáculos, existem diferentes tipos de técnicas para evitar colisões que consideram os efeitos cinemáticos e dinâmicos na obtenção de trajetórias com o menor tempo, torque, etc. Neste estudo, são propostas contribuições à aplicação dessas técnicas especificamente a robôs manipuladores pneumáticos, sobretudo, no que diz respeito às características específicas dos servoposicionadores pneumáticos, como, por exemplo, a modelagem do atrito desses sistemas, o cálculo da massa equivalente, etc. A metodologia utilizada é definida em duas etapas. A primeira delas consiste na obtenção de pontos intermediários, adquiridos considerando a menor distância entre os mesmos e o ponto final, gerados considerando a presença de obstáculos (cilindros, cubos e esferas) Esses obstáculos são mapeados em regiões de colisão, que constituem restrições para o problema de otimização. A segunda etapa baseia-se no estudo do planejamento de trajetórias: aplicam-se b-splines de 5º e 7º grau na interpolação dos pontos intermediários, com vistas à obtenção de trajetórias que considerem, de um lado, a menor força dos atuadores associada à dinâmica do manipulador em estudo e, de outro, restrições cinemáticas e dinâmicas, determinadas por meio das características operacionais dos servoposicionadores pneumáticos. Os resultados mostram que a metodologia proposta é adequada para tarefas de manipulação de peças na presença de obstáculos, uma vez que os pontos intermediários situam-se fora da região de colisão nos três casos aqui apresentados. Além disso, quanto à segunda etapa, observou-se que as trajetórias de 5º e 7º grau apresentaram resultados similares, de maneira que os erros obtidos poderiam ser melhorados analisando aspectos associados ao controlador do robô em estudo. / The thesis presents a study for collision-free trajectory planning for a pneumatic robot with 5 degrees of freedom applying three metaheuristic algorithms: firefly metaheuristic algorithm, particle swarm optimization and genetic algorithms. As regards the application of metaheuristic algorithms to the study of the trajectory planning of manipulating robots in the presence of obstacles, there are different types of techniques to avoid collisions that consider the kinematic and dynamic effects, obtaining trajectories with the optimal time, torque, etc. In this study, contributions are made to the application of these techniques specifically to pneumatic manipulator robots, particularly with regard to the specific characteristics of pneumatic servo-actuators, such as friction modeling of these systems, calculation of equivalent mass, etc. The methodology used is defined in two steps. The first one consists of obtaining intermediate points, acquired considering the smallest distance between the intermediate points and the final point, generated considering the presence of obstacles (cylinders, cubes and spheres) These obstacles are mapped in collision regions, which are constraints to the optimization problem. The second step is based on the study of the trajectory planning: 5th and 7th degree b-splines are applied in the interpolation of the intermediate points, in order to obtain trajectories that consider the smallest actuator force associated to the dynamics of the manipulator and the kinematic and dynamic constraints, determined by the operational characteristics of pneumatic servo-positioners. The results show that the proposed methodology is suitable for tasks of manipulating parts in the presence of obstacles because the intermediate points are outside the collision region in the three cases presented here. In addition, it was observed that the trajectories of 5th and 7th degree presented similar results, so that the errors obtained could be improved by analyzing aspects associated to the controller of the robot.

Submitted by Clebson Anjos (clebson.leandro54@gmail.com) on 2016-02-15T20:03:45Z No. of bitstreams: 1 arquivototal.pdf: 2424729 bytes, checksum: 0b742be3286a70e0901c3d5a00813f6f (MD5) / Made available in DSpace on 2016-02-15T20:03:45Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 2424729 bytes, checksum: 0b742be3286a70e0901c3d5a00813f6f (MD5) Previous issue date: 2015-08-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / One of the main issues related to the mobile robotics area is to find the most efficient way to perform the navigation from one point to another over environments, considering maximum safety and spending as less as possible time and computer resources. From this perspective, the aim of this work was to specify improved heuristics that could be applicable to cost functions of key A* based algorithms and use, more efficiently, the available computational resources. In this way, our approach aimed at minimizing the amount of collisions, the length of paths, and the processing time by minimizing the importance of g(n) term, which accounts for storing information from past steps of A* family algorithms. To show the effects of this modification, a survey of the best search strategies in dynamic and static environments was carried out and, after that, we analyzed the four best and latest algorithms, according to the specialized literature. Some comparisons have been made considering static and highly dynamic environments with different directions and search parameters to measure the quality of generated paths. Then, these algorithms were again analyzed with their cost functions modified according to our approach. The results of the comparison show that the R* algorithm, with forward search, is the most efficient for different spaces and searches. However, the change in their respective cost functions provided a significant improvement in the already excellent results achieved by the algorithms. In static environments, this modification showed up to be more effective for large and complex problems, which are commonly used for real robots. In highly dynamic environments, the cost function modification provided a considerable reduction in the time of planning and number of iterations to find the goal, as well as reductions in the memory utilization. / Uma das principais questões relacionados ao tema da robótica móvel é descobrir a maneira mais eficiente para realizar a navegação, de um ponto a outro no ambiente, com máxima segurança e despendendo a menor quantidade de tempo e de recursos computacionais possível. À vista disso, o presente trabalho se motiva a desenvolver uma melhoria heurística que possa ser aplicável às funções custo dos principais algoritmos baseados na família A* e que propõe utilizar, de forma mais eficiente, os recursos computacionais disponíveis, aperfeiçoando assim, os resultados obtidos através dos principais algoritmos de buscas aplicados à robótica móvel. A mesma tem o objetivo de minimizar a quantidade de colisões, a duração do trajeto, bem como o tempo de processamento através da minimização da importância da variável g(n) - responsável em armazenar informações subutilizadas do passado dos algoritmos. Para visualizar os efeitos dessa modificação, um levantamento das melhores estratégias de busca em ambiente estático e dinâmico foi realizado e, através deste, foram analisados os quatro melhores e mais atuais algoritmos destacados pela literatura técnica especializada. Algumas comparações foram efetuadas considerando ambientes estáticos e altamente dinâmico com diferentes direções de busca e parâmetros que visavam mensurar a qualidade das trajetórias geradas. Em seguida, esses foram novamente analisados com suas respectivas funções custo modificada. Os resultados da comparação demonstraram que o algoritmo R*, com direção de busca direta, é o mais eficiente para diferentes espaços e pesquisas. No entanto, a modificação em suas respectivas funções custo proporcionou uma melhora significativa nos resultados conquistados pelos algoritmos originais. Em ambientes estáticos, esta modificação se mostrou mais eficaz para problemas grandes e complexos, os que são efetivamente utilizados por robôs reais. Em ambientes altamente dinâmicos, a mesma apresentou uma redução considerável no tempo de planejamento e no número de iterações para localizar o objetivo, bem como reduziu a utilização de memória o que, consequentemente, tornou os robôs mais ágeis e habilidosos.