Task Assignment For Robots In Challenging Environments

The task assignment problem for multiple robots/vehicles has been increasingly exploited to enable robots to effectively and efficiently accomplish complex and dangerous missions.In particular,the task assignment for one or multiple robots to visit a set of target locations,while minimizing some objective such as the robots' total travel time/distance,has been an important research area due to its high theoretical value and wide engineering applications in logistics,terrain mapping,environmental monitoring,disaster rescue,and military combat.The current research works on the task assignment of multiple robots have the following limitations: First,most of state-of-the-art task assignment algorithms have been developed under the restrictive assumption of no external disturbance,in which the optimal manner for a robot to travel through two locations is to travel along the straight line connecting the two locations.When a robot's motion is affected by external disturbance such as winds or currents in a drift field,traveling along the strait line connecting two locations is generally not energy/time optimal anymore.Apart from that,a robot with limited thrust power might be unable to travel from an initial location to a target location in a drift field with strong currents/winds.As a result,for the multi-robot task assignment with external disturbance,it is necessary to investigate how to plan a path for a robot to optimally travel through two prescribed locations and how to assign the reachable target locations to the robots.Second,current research mainly focuses on the static multi-robot task assignment problem in which the information on all the target locations to be visited is initially known.However,some new target locations might dynamically appear.Third,in the current research on the multi-robot task assignment problems,the accomplishment of one task is generally independent of the other tasks.However,in applications of logistics,terrain mapping and environmental monitoring,some customers/targets can have priority over others due to their importance or urgency to be served.As a result,it is meaningful to investigate the task assignment problem with precedence constraints.Focused on the limitations of the current research works previously discussed,this thesis studies the task assignment problem for robots in challenging environments.The main works and the contributions of the thesis are described as follows:(1)Single-robot task assignment with precedence constraintsThis thesis first studies the precedence-constrained task assignment problem where one single robot needs to visit a set of target locations subject to precedence constraints that specify which targets need to be visited before which other targets.The objective is to minimize the robot's total travel distance to visit all the targets while satisfying every precedence constraint.The problem is shown to be NP-hard,and consequently to measure the proximity of a sub-optimal solution from the optimal,we construct a lower bound on the optimal solution using tools from graph theory.Then,inspired by the existing topological sorting techniques,a new topological sorting strategy is proposed.In addition,facilitated by the sorting,we propose several heuristic algorithms to solve the task assignment problem.Numerical experiments show that the algorithms can quickly lead to satisfying solutions and have superior performance compared with popular genetic algorithms.(2)Multi-robot dynamic task assignmentSecond,this thesis investigates the dynamic task assignment problem in which multiple dispersed robots are employed to visit a set of targets where some targets' locations are initially known and the others are dynamically randomly appear during a finite time horizon.The objective is to visit all the target locations while trying to minimize the robots' total travel time.To investigate what the appropriate time instants should be to change,in real time,the assignment of the target locations in response to the newly generated target locations,two types of dynamic task assignment mechanisms,namely event-triggered and time-triggered,are first studied.Furthermore,for both the event and time-triggered assignment mechanisms,we propose several algorithms to investigate how to distribute the newly generated target locations to the robots to minimize their total travel time.Monte Carlo simulations are carried out which show the better performance of the event-triggered task assignment algorithms over the time-triggered algorithms under different arrival rates of the newly generated target locations.(3)Multi-robot task assignment in a drift fieldThis thesis also investigates the task assignment problem for a fleet of robots to deliver a number of customized sensors to a set of target locations in a planar lateral time-varying drift field.First,to enable a robot to travel between two given positions in the drift field with the minimum time,a path planning algorithm is designed based on the accessible area analysis and optimal control theory.Second,to assign the target locations to the robots,we propose a co-evolutionary multi-population genetic algorithm that integrates the intermarriage crossover mechanism with a multiple offspring strategy,and utilizes a virtual coding technique together with a tabu mechanism.A novel solution to the challenging sensor delivery task assignment problem for multiple robots is obtained after incorporating the path planning algorithm and the CMGA algorithm.Simulations on the task assignment for multiple robots in both time-invariant and time-varying drift fields show the satisfying performances of the proposed approach against popular greedy algorithms.(4)Multi-robot task assignment with unreachable target locationsLast,for the multi-robot task assignment with unreachable target locations,this thesis studies how to visit as many target locations as possible by using the minimum number of robots while minimizing the robots' total travel time.To use the minimum number of robots to visit the maximum number of target locations,we first propose a target merging strategy to optimize the problem.Then,we analyze the computational complexity for optimizing the problem,and find that the problem is in general NP-hard if more than one robot can be employed to visit the target locations.Furthermore,we design a heuristic task assignment algorithm and analyze the cases in which the objective to visit the maximum number of targets by using the minimum number of robots can be obtained through the proposed algorithm within linear running time.Once the targets to be visited and the corresponding employed robots are determined,one of the proposed marginalcost based target inserting principles guarantees that the chosen targets will be visited within a computable finite maximal travel time,which is at most,twice the optimal when the cost matrix is symmetric.Numerical simulations show that the proposed algorithms can lead to near optimal solutions.