An optimal path planning problem for heterogeneous multi-vehicle systems

• Autorzy: Klaučo M. , Blažek S. , Kvasnica M.

Identyfikatory

DOI

10.1515/amcs-2016-0021

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

path planning; multi vehicle system; mixed-integer programming

PL

planowanie ruchu; system wielopojazdowy; programowanie całkowitoliczbowe

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2016
• Tom: Vol. 26, no. 2
• Strony: 297--308
• Opis fizyczny: Bibliogr. 15 poz., rys., tab., wykr.

Twórcy

autor

Klaučo M.

• Institute of Information Engineering, Automation and Mathematics, Slovak University of Technology in Bratislava, Radlinského 9, Bratislava, Slovakia

autor

Blažek S.

• Institute of Information Engineering, Automation and Mathematics, Slovak University of Technology in Bratislava, Radlinského 9, Bratislava, Slovakia

autor

Kvasnica M.

• Institute of Information Engineering, Automation and Mathematics, Slovak University of Technology in Bratislava, Radlinského 9, Bratislava, Slovakia

Bibliografia

• [1] Applegate, D. (2006). The Traveling Salesman Problem: A Computational Study, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ.
• [2] Boyd, S. and Vandenberghe, L. (2009). Convex Optimization, 7th Edn., Cambridge University Press, New York, NY.
• [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.
• [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.
• [14] Tung, D.V. and Pinnoi, A. (2000). Vehicle routingscheduling for waste collection in Hanoi, European Journal of Operational Research 125(3): 449–468.
• [15] Williams, H. (1993). Model Building in Mathematical Programming, 3rd Edn., John Wiley & Sons, Hoboken, NJ.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.