This thesis deals with the no-depot minmax Multiple Traveling Salesmen Problem (MTSP), which can be formulated as follows. Given a set of n cities and k salesmen,find k disjoint tours (one for each salesmen) such that each city belongs to exactly one tour and the length of the longest of k tours is minimized. The no-depot assumption means that the salesmen do not start from and return to one fixed depot. The no-depot model can be applied in designing patrolling routes, as well as in business situations, especially where salesmen work from home or the company has no central office. This model can be also applied to the job scheduling problem with n jobs and k identical machines. Despite its potential applicability to a number of important situations, the research literature on the no-depot minmax k-TSP has been limited, with no reports on computational experiments. The previously published results included the proof of NP-hardness of the problem of interest, which motivates using heuristics for its solution. This thesis proposes several construction heuristic algorithms, including greedy algorithms, cluster first and route second algorithms, and route first and cluster second algorithms. As a local search method for a single tour, 2-opt search and Lin-Kernighan were used, and for a local search method between multiple tours, relocation and exchange (edge heuristics) were used. Furthermore, to prevent the drawback of trapping in the local minima, the simulated annealing method is used. Extensive computational experiments were carried out using TSPLIB instances. Among construction algorithms, route first and cluster second algorithms including removing two edges method performed best. In terms of running time, clustering first and routing second algorithms took shorter time on large-scale instances. The simulated annealing could produce better solutions than the descent method, but did not always perform well in terms of average solution. To evaluate the performance of the proposed heuristic methods, their solutions were compared with the optimal solutions obtained using a mixed-integer programming formulation of the problem. For small-scale problems, heuristic solutions were equal to the optimal solution output by CPLEX.

O Brasil é uma referência mundial na produção e exportação de citros, entretanto esse cultivo pode sofrer diversos problemas e perdas de produtividade por motivos diversos, como por exemplo, pragas. Para reduzir os riscos e perdas, torna-se interessante o uso de sistemas automatizados de monitoramento, justificando a necessidade de realizar a coleta de dados para determinar diversos fatores. Determinadas plantações, como a de citros, não podem ser monitoradas somente via solo ou somente via imagens aéreas, tornando necessário mesclar ambas as abordagens de acordo com o parâmetro a ser monitorado. Para a realização desse monitoramento devem ser utilizados robôs com habilidades distintas, robôs aéreos e robôs terrestres. Assim, é preciso designar as tarefas que cada robô realizará e também coordenar todos os robôs durante a execução do sistema como um todo, visando otimizar o processo de coleta de dados. Esse problema pode ser analisado e modelado como um problema de alocação de tarefas para robôs (Multi-Robot Task Allocation (MRTA)). Para resolver esse problema propõe-se um framework baseado em técnicas de cobertura de conjuntos e em mecanismo de mercado baseado em leilão. Teste simulados são realizados e demonstram que a presente proposta cumpre o papel na alocação das tarefas aos robôs. Além disso, visando a aplicação da solução proposta é projetado e desenvolvido uma plataforma robótica aérea (quadrirotor) de baixo custo utilizando peças prototipadas. Para o controle de estabilidade dessa plataforma, propõe-se um modelo matemático de acordo com os parâmetros inerciais do quadrirotor. Esse quadrirotor é utilizado em diversas aplicações reais, mostrando que o projeto desenvolvido pode ser reproduzido e destinado a execução de tarefas reais, como por exemplo a coleta de dados na agricultura de precisão. / Brazil is a world reference in the production and export of citrus, although this crop can suffer several problems and losses of productivity for diverse reasons, as for example, pests. In order to reduce risks and losses, it is interesting to use automated monitoring systems, justifying the need to perform data collection to determine several factors. Certain plantations, such as citrus plantations, can not be monitored only via soil or only via aerial images, making it necessary to merge both approaches according to the parameter to be monitored. To perform this monitoring, robots with different abilities, such asunmanned aerial vehicle (UAV) and unmanned ground vehicle (UCV) should be used. Therefore, it is necessary to assign the tasks that each robot will perform and also to coordinate all the robots during the execution of the system as a whole, in order to optimize the process of data collection. The problem can be studied and modeled as a task allocation problem for robots (MRTA). To solve this problem we propose a framework based set covering techniques and auction-based market mechanism. Simulated tests are performed and demonstrate that the present proposal fulfills the role in assigning tasks to robots. In addition, aiming at the application of the proposed solution is designed and developed a low cost aerial robotic platform (quadrirotor) which use prototyped parts. This quadrirotor is used in several real applications, showing that the developed project can be reproduced and destined to perform real tasks, such as data collection in precision agriculture.

O Brasil é uma referência mundial na produção e exportação de citros, entretanto esse cultivo pode sofrer diversos problemas e perdas de produtividade por motivos diversos, como por exemplo, pragas. Para reduzir os riscos e perdas, torna-se interessante o uso de sistemas automatizados de monitoramento, justificando a necessidade de realizar a coleta de dados para determinar diversos fatores. Determinadas plantações, como a de citros, não podem ser monitoradas somente via solo ou somente via imagens aéreas, tornando necessário mesclar ambas as abordagens de acordo com o parâmetro a ser monitorado. Para a realização desse monitoramento devem ser utilizados robôs com habilidades distintas, robôs aéreos e robôs terrestres. Assim, é preciso designar as tarefas que cada robô realizará e também coordenar todos os robôs durante a execução do sistema como um todo, visando otimizar o processo de coleta de dados. Esse problema pode ser analisado e modelado como um problema de alocação de tarefas para robôs (Multi-Robot Task Allocation (MRTA)). Para resolver esse problema propõe-se um framework baseado em técnicas de cobertura de conjuntos e em mecanismo de mercado baseado em leilão. Teste simulados são realizados e demonstram que a presente proposta cumpre o papel na alocação das tarefas aos robôs. Além disso, visando a aplicação da solução proposta é projetado e desenvolvido uma plataforma robótica aérea (quadrirotor) de baixo custo utilizando peças prototipadas. Para o controle de estabilidade dessa plataforma, propõe-se um modelo matemático de acordo com os parâmetros inerciais do quadrirotor. Esse quadrirotor é utilizado em diversas aplicações reais, mostrando que o projeto desenvolvido pode ser reproduzido e destinado a execução de tarefas reais, como por exemplo a coleta de dados na agricultura de precisão. / Brazil is a world reference in the production and export of citrus, although this crop can suffer several problems and losses of productivity for diverse reasons, as for example, pests. In order to reduce risks and losses, it is interesting to use automated monitoring systems, justifying the need to perform data collection to determine several factors. Certain plantations, such as citrus plantations, can not be monitored only via soil or only via aerial images, making it necessary to merge both approaches according to the parameter to be monitored. To perform this monitoring, robots with different abilities, such asunmanned aerial vehicle (UAV) and unmanned ground vehicle (UCV) should be used. Therefore, it is necessary to assign the tasks that each robot will perform and also to coordinate all the robots during the execution of the system as a whole, in order to optimize the process of data collection. The problem can be studied and modeled as a task allocation problem for robots (MRTA). To solve this problem we propose a framework based set covering techniques and auction-based market mechanism. Simulated tests are performed and demonstrate that the present proposal fulfills the role in assigning tasks to robots. In addition, aiming at the application of the proposed solution is designed and developed a low cost aerial robotic platform (quadrirotor) which use prototyped parts. This quadrirotor is used in several real applications, showing that the developed project can be reproduced and destined to perform real tasks, such as data collection in precision agriculture.

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.

The motion planning problem can be formulated as a Markov decision process (MDP), if the uncertainties in the robot motion and environments can be modeled probabilistically. The complexity of solving these MDPs grow exponentially as the dimension of the problem increases and hence, it is nearly impossible to solve the problem even without constraints. Using hierarchical methods, these MDPs can be transformed into a semi-Markov decision process (SMDP) which only needs to be solved at certain landmark states. In the deterministic robotics motion planning community, sampling based algorithms like probabilistic roadmaps (PRM) and rapidly exploring random trees (RRTs) have been successful in solving very high dimensional deterministic problem. However they are not robust to system with uncertainties in the system dynamics and hence, one of the primary objective of this work is to generalize PRM/RRT to solve motion planning with uncertainty. We first present generalizations of randomized sampling based algorithms PRM and RRT, to incorporate the process uncertainty, and obstacle location uncertainty, termed as "generalized PRM" (GPRM) and "generalized RRT" (GRRT). The controllers used at the lower level of these planners are feedback controllers which ensure convergence of trajectories while mitigating the effects of process uncertainty. The results indicate that the algorithms solve the motion planning problem for a single agent in continuous state/control spaces in the presence of process uncertainty, and constraints such as obstacles and other state/input constraints. Secondly, a novel adaptive sampling technique, termed as "adaptive GPRM" (AGPRM), is proposed for these generalized planners to increase the efficiency and overall success probability of these planners. It was implemented on high-dimensional robot n-link manipulators, with up to 8 links, i.e. in a 16-dimensional state-space. The results demonstrate the ability of the proposed algorithm to handle the motion planning problem for highly non-linear systems in very high-dimensional state space. Finally, a solution methodology, termed the "multi-agent AGPRM" (MAGPRM), is proposed to solve the multi-agent motion planning problem under uncertainty. The technique uses a existing solution technique to the multiple traveling salesman problem (MTSP) in conjunction with GPRM. For real-time implementation, an ?inter-agent collision detection and avoidance? module was designed which ensures that no two agents collide at any time-step. Algorithm was tested on teams of homogeneous and heterogeneous agents in cluttered obstacle space and the algorithm demonstrate the ability to handle such problems in continuous state/control spaces in presence of process uncertainty.