Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

A mixed integer linear programming approach to pursuit evasion problems with optional connectivity constraints Thunberg, Johan ; 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 ▲] Detailed reference viewed: 112 (0 UL)A boolean control network approach to pursuit evasion problems in polygonal environments Thunberg, Johan ; ; in Proceedings of the 2011 IEEE International Conference on Robotics and Automation (ICRA) (2011) In this paper, the multi pursuer version of the pursuit evasion problem in polygonal environments is addressed. This problem is NP-hard, and therefore we seek good enough, but not optimal solutions. By ... [more ▼] In this paper, the multi pursuer version of the pursuit evasion problem in polygonal environments is addressed. This problem is NP-hard, and therefore we seek good enough, but not optimal solutions. By modeling the problem as a Boolean Control Network, we can efficiently keep track of which regions are cleared, and which are not, while the input nodes of the network are used to represent the motion of the pursuers. The environment is partitioned into a set of convex regions, where each region correspond to a set of nodes in the network. The method is implemented in ANSI C, and efficiently solves complex environments containing multiple loops and requiring so-called recontamination. The provided examples demonstrate the effectiveness of the method in terms of computational time. [less ▲] Detailed reference viewed: 93 (0 UL)An iterative Mixed Integer Linear Programming Approach to pursuit evasion problems in polygonal environments Thunberg, Johan ; 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 ▲] Detailed reference viewed: 123 (0 UL)Towards optimal positioning of surveillance UGVs ; ; Thunberg, Johan in Optimization and Cooperative Control Strategies (2009) Unmanned Ground Vehicles (UGVs) equipped with surveillance cameras present a flexible complement to the numerous stationary sensors being used in security applications today. However, to take full ... [more ▼] Unmanned Ground Vehicles (UGVs) equipped with surveillance cameras present a flexible complement to the numerous stationary sensors being used in security applications today. However, to take full advantage of the flexibility and speed offered by a group of UGV platforms, a fast way to compute desired camera locations to cover an area or a set of buildings, e.g., in response to an alarm, is needed. Building upon earlier results in terrain guarding and sensor placement we propose a way to find candidate guard positions that satisfy a large set of view angle and range constraints simulataneously. Since the original problem is NP-complete, we do not seek to find the true optimal set of guard positions. Instead, a near optimal subset of the candidate points is chosen using a scheme with a known approximation ratio of O(log(n)). A number of examples are presented to illustrate the approach. [less ▲] Detailed reference viewed: 97 (1 UL)A comparative study of task assignment and path planning methods for multi-UGV missions Thunberg, Johan ; ; 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 ▲] Detailed reference viewed: 87 (0 UL)Optimal positioning of surveillance UGVs ; ; Thunberg, Johan in Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (2008) Unmanned ground vehicles (UGVs) equipped with surveillance cameras present a flexible complement to the numerous stationary sensors being used in security applications today. However, to take full ... [more ▼] Unmanned ground vehicles (UGVs) equipped with surveillance cameras present a flexible complement to the numerous stationary sensors being used in security applications today. However, to take full advantage of the flexibility and speed offered by a group of UGV platforms, a fast way to compute desired camera locations that cover or surround a set of buildings e.g., in response to an alarm, is needed. In this paper we focus on two problems. The first is how to create a line-of-sight perimeter around a given set of buildings with a minimal number of UGVs. The second problem is how to find UGV positions such that a given set of walls are covered by the cameras while taking constraints in terms of zoom, range, resolution and field of view into account. For the first problem we propose a polynomial time algorithm and for the second problem we extend our previous work to include zoom cameras and furthermore provide a theoretical analysis of the approach itself. A number of examples are presented to illustrate the two algorithms. [less ▲] Detailed reference viewed: 116 (0 UL) |
||