An iterative mixed integer linear programming approach to pursuit evasion problems in polygonal environments
(2010) 2010 IEEE International Conference on Robotics and Automation, ICRA 2010 In Proceedings - IEEE International Conference on Robotics and Automation p.5498-5503- Abstract
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... (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)
- author
- Thunberg, Johan LU and Ögren, Petter
- publishing date
- 2010
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 2010 IEEE International Conference on Robotics and Automation, ICRA 2010
- series title
- Proceedings - IEEE International Conference on Robotics and Automation
- article number
- 5509438
- pages
- 6 pages
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 2010 IEEE International Conference on Robotics and Automation, ICRA 2010
- conference location
- Anchorage, AK, United States
- conference dates
- 2010-05-03 - 2010-05-07
- external identifiers
-
- scopus:77955777875
- ISSN
- 1050-4729
- ISBN
- 9781424450381
- DOI
- 10.1109/ROBOT.2010.5509438
- language
- English
- LU publication?
- no
- id
- e42d7ec0-0883-45a1-aba5-8b503d0785b0
- date added to LUP
- 2024-09-05 12:49:52
- date last changed
- 2024-09-23 16:18:09
@inproceedings{e42d7ec0-0883-45a1-aba5-8b503d0785b0,
abstract = {{<p>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.</p>}},
author = {{Thunberg, Johan and Ögren, Petter}},
booktitle = {{2010 IEEE International Conference on Robotics and Automation, ICRA 2010}},
isbn = {{9781424450381}},
issn = {{1050-4729}},
language = {{eng}},
pages = {{5498--5503}},
publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
series = {{Proceedings - IEEE International Conference on Robotics and Automation}},
title = {{An iterative mixed integer linear programming approach to pursuit evasion problems in polygonal environments}},
url = {{http://dx.doi.org/10.1109/ROBOT.2010.5509438}},
doi = {{10.1109/ROBOT.2010.5509438}},
year = {{2010}},
}