A mixed integer linear programming approach to pursuit evasion problems with optional connectivity constraints

in Autonomous Robots (2011), 31(4), 333-343

In this paper, we address the multi pursuer version of the pursuit evasion problem in polygonal environments. By discretizing the problem, and applying a Mixed Integer Linear Programming (MILP) framework ... [more ▼]

In this paper, we address the multi pursuer version of the pursuit evasion problem in polygonal environments. By discretizing the problem, and applying a Mixed Integer Linear Programming (MILP) framework, we are able to address problems requiring so-called recontamination and also impose additional constraints, such as connectivity between the pursuers. The proposed MILP formulation is less conservative than solutions based on graph discretizations of the environment, but still somewhat more conservative than the original underlying problem. It is well known that MILPs, as well as multi pursuer pursuit evasion problems, are NP-hard. Therefore we apply an iterative Receding Horizon Control (RHC) scheme where a number of smaller MILPs are solved over shorter planning horizons. The proposed approach is implemented in Matlab/Cplex and illustrated by a number of solved examples. [less ▲]

An iterative Mixed Integer Linear Programming Approach to pursuit evasion problems in polygonal environments

in Proceedings of the 2010 IEEE International Conference on Robotics and Automation (ICRA) (2010)

In this paper, we address the multi pursuer version of the pursuit evasion problem in polygonal environments. It is well known that this problem is NP-hard, and therefore we seek efficient, but not ... [more ▼]

In this paper, we address the multi pursuer version of the pursuit evasion problem in polygonal environments. It is well known that this problem is NP-hard, and therefore we seek efficient, but not optimal, solutions by relaxing the problem and applying the tools of Mixed Integer Linear Programming (MILP) and Receding Horizon Control (RHC). Approaches using MILP and RHC are known to produce efficient algorithms in other path planning domains, such as obstacle avoidance. Here we show how the MILP formalism can be used in a pursuit evasion setting to capture the motion of the pursuers as well as the partitioning of the pursuit search region into a cleared and a contaminated part. RHC is furthermore a well known way of balancing performance and computation requirements by iteratively solving path planning problems over a receding planning horizon, and adapt the length of that horizon to the computational resources available. The proposed approach is implemented in Matlab/Cplex and illustrated by a number of solved examples. [less ▲]

A comparative study of task assignment and path planning methods for multi-UGV missions

in Optimization and Cooperative Control Strategies (2009)

Many important problems involving a group of unmanned ground vehicles (UGVs) are closely related to the multi traviling salesman problem (m-TSP). This paper comprises a comparative study of a number of ... [more ▼]

Many important problems involving a group of unmanned ground vehicles (UGVs) are closely related to the multi traviling salesman problem (m-TSP). This paper comprises a comparative study of a number of algorithms proposed in the litterature to solve m-TSPs occuring in robotics. The investigated algoritms include two mixed integer linear programming (MILP) formulations, a market based approach (MA), a Voronoi partition step (VP) combined with the local search used in MA, and a deterministic and a stocastic version of the granular tabu search (GTS). To evaluate the algoritms, an m-TSP is derived from a planar environment with polygonal obstacles and uniformly distributed targets and vehicle positions. The results of the comparison indicate that out of the decentralized approaches, the MA yield good solutions but requires long computation times, while VP is fast but not as good. The two MILP approaches suffer from long computation times, and poor results due to the decomposition of the assignment and path planning steps. Finally, the two GTS algorithms yield good results in short times with inputs from MA as well as the much faster VP. Thus the best performing centralized approach is the GTS in combination with the VP. [less ▲]