An optimal path planning problem for heterogeneous multi-vehicle systems

Martin Klaučo; Slavomír Blažek; Michal Kvasnica

International Journal of Applied Mathematics and Computer Science (2016)

  • Volume: 26, Issue: 2, page 297-308
  • ISSN: 1641-876X

Abstract

top
A path planning problem for a heterogeneous vehicle is considered. Such a vehicle consists of two parts which have the ability to move individually, but one of them has a shorter range and is therefore required to keep in a close distance to the main vehicle. The objective is to devise an optimal path of minimal length under the condition that at least one part of the heterogeneous system visits all desired waypoints exactly once. Two versions of the problem are considered. One assumes that the order in which the waypoints are visited is known a priori. In such a case we show that the optimal path can be found by solving a mixed-integer second-order cone problem. The second version assumes that the order in which the waypoints are visited is not known a priori, but can be optimized so as to shorten the length of the path. Two approaches to solve this problem are presented and evaluated with respect to computational complexity.

How to cite

top

Martin Klaučo, Slavomír Blažek, and Michal Kvasnica. "An optimal path planning problem for heterogeneous multi-vehicle systems." International Journal of Applied Mathematics and Computer Science 26.2 (2016): 297-308. <http://eudml.org/doc/280110>.

@article{MartinKlaučo2016,
abstract = {A path planning problem for a heterogeneous vehicle is considered. Such a vehicle consists of two parts which have the ability to move individually, but one of them has a shorter range and is therefore required to keep in a close distance to the main vehicle. The objective is to devise an optimal path of minimal length under the condition that at least one part of the heterogeneous system visits all desired waypoints exactly once. Two versions of the problem are considered. One assumes that the order in which the waypoints are visited is known a priori. In such a case we show that the optimal path can be found by solving a mixed-integer second-order cone problem. The second version assumes that the order in which the waypoints are visited is not known a priori, but can be optimized so as to shorten the length of the path. Two approaches to solve this problem are presented and evaluated with respect to computational complexity.},
author = {Martin Klaučo, Slavomír Blažek, Michal Kvasnica},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {path planning; multi-vehicle system; mixed-integer programming},
language = {eng},
number = {2},
pages = {297-308},
title = {An optimal path planning problem for heterogeneous multi-vehicle systems},
url = {http://eudml.org/doc/280110},
volume = {26},
year = {2016},
}

TY - JOUR
AU - Martin Klaučo
AU - Slavomír Blažek
AU - Michal Kvasnica
TI - An optimal path planning problem for heterogeneous multi-vehicle systems
JO - International Journal of Applied Mathematics and Computer Science
PY - 2016
VL - 26
IS - 2
SP - 297
EP - 308
AB - A path planning problem for a heterogeneous vehicle is considered. Such a vehicle consists of two parts which have the ability to move individually, but one of them has a shorter range and is therefore required to keep in a close distance to the main vehicle. The objective is to devise an optimal path of minimal length under the condition that at least one part of the heterogeneous system visits all desired waypoints exactly once. Two versions of the problem are considered. One assumes that the order in which the waypoints are visited is known a priori. In such a case we show that the optimal path can be found by solving a mixed-integer second-order cone problem. The second version assumes that the order in which the waypoints are visited is not known a priori, but can be optimized so as to shorten the length of the path. Two approaches to solve this problem are presented and evaluated with respect to computational complexity.
LA - eng
KW - path planning; multi-vehicle system; mixed-integer programming
UR - http://eudml.org/doc/280110
ER -

References

top
  1. Applegate, D. (2006). The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ. Zbl1130.90036
  2. Boyd, S. and Vandenberghe, L. (2009). Convex Optimization, 7th Edn., Cambridge University Press, New York, NY. Zbl1058.90049
  3. Fagerholt, K. (1999). Optimal fleet design in a ship routing problem, International Transactions in Operational Research 6(5): 453-464. 
  4. Garone, E., Determe, J.-F. and Naldi, R. (2012). A travelling salesman problem for a class of heterogeneous multi-vehicle systems, 2012 IEEE 51st Annual Conference on Decision and Control (CDC), Maui, HI, USA, pp. 1166-1171. 
  5. Gurobi Optimization (2013). Gurobi optimizer reference manual, http://www.gurobi.com. 
  6. Hoff, A., Andersson, H., Christiansen, M., Hasle, G. and Lkketangen, A. (2010). Industrial aspects and literature survey: Fleet composition and routing, Computers & Operations Research 37(12): 2041 - 2061. Zbl1231.90091
  7. ILOG (2007). 11.0 users manual, ILOG CPLEX Division, Incline Village, NV. 
  8. Kerrigan, E. and Maciejowski, J. (2000). Soft constraints and exact penalty functions in model predictive control, Control 2000 Conference, Cambridge, UK. 
  9. Klaučo, M., Blažek, S., Kvasnica, M. and Fikar, M. (2014). Mixed-integer SOCP formulation of the path planning problem for heterogeneous multi-vehicle systems, European Control Conference 2014, Strasbourg, France, pp. 1474-1479. 
  10. Kvasnica, M. (2008). Efficient Software Tools for Control and Analysis of Hybrid Systems, Ph.D. thesis, ETH Zurich, Zurich. 
  11. Löfberg, J. (2004). YALMIP, http://users.isy.liu. se/johanl/yalmip/. 
  12. Mathew, N., Smith, S. and Waslander, S. (2014). Optimal path planning in cooperative heterogeneous multi-robot delivery systems, 11th International Workshop on the Algorithmic Foundations of Robotics, Istanbul, Turkey. 
  13. Miller, C.E., Tucker, A.W. and Zemlin, R.A. (1960). Integer programming formulation of traveling salesman problems, Journal of the ACM 7(4): 326-329. Zbl0100.15101
  14. Tung, D.V. and Pinnoi, A. (2000). Vehicle routingscheduling for waste collection in Hanoi, European Journal of Operational Research 125(3): 449 - 468. Zbl0967.90020
  15. Williams, H. (1993). Model Building in Mathematical Programming, 3rd Edn., John Wiley & Sons, Hoboken, NJ. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.