Abstract
In this paper, we consider a task allocation model that consists of assigning a set of m unmanned aerial vehicles (UAVs) to a set of n tasks in an optimal way. The optimality is quantified by target scores. The mission is to maximize the target score while satisfying capacity constraints of both the UAVs and the tasks. This problem is known to be NP-hard. Existing algorithms are not suitable for the large scale setting. Scalability and robustness are recognized as two main issues. We deal with these issues by two optimization approaches. The first approach is the Cross-Entropy (CE) method, a generic and practical tool of stochastic optimization for solving NP-hard problem. The second one is Branch and Bound algorithm, an efficient classical tool of global deterministic optimization. The numerical results show the efficiency of our approaches, in particular the CE method for very large scale setting.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Pham Dinh T., Le Thi H.A.: Convex analysis approach to DC programming: theory, algorithms and applications (dedicated to Professor Hoang Tuy on the occasion of his 70th birthday). Acta Math. Vietnamica 22, 289–355 (1997)
Le Thi H.A., Pham Dinh T.: Large scale global molecular optimization from exact distance matrices by a DC optimization approach. SIAM J. Optim. 14(1), 77–114 (2003)
Le Thi H.A., Pham Dinh T.: The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133, 23–46 (2005)
Chandler, P.R., Pachter, M., Rasmussen, S.R., Schumacher, C.: Multiple Task Assignment for a UAV Team. AIAA Guidance, navigation, and control conference, Monterey, Aug. (2002)
Costa A., Dafydd O., Kroese D.: Convergence properties of the cross-entropy method for discrete optimization. Oper. Res. Lett. 35(5), 57380 (2007)
Cruz, J.B. Jr., Chen, G., Li D., Wang, X.: Particle swarm optimization for resource allocation in UAV cooperative control. AIAA Guidance, Navigation, and Control Conference, Providence, Aug. (2004)
Fontes D.B.M.M., Fontes F.A.C.C.: Minimal switching time formations with collision avoidance. Dyn. Inf. Syst. Springer Optim. Appl. 40, 305–321 (2010)
Dambreville, F.: Cross-entropy method: convergence issues for extended implementation. In: Proceedings of the Rare Event Simulation Conference (RESIM 2006), Bamberg, Germany (2006)
Walker D.H., McLain T.W., Howlett J.K.: Coordinated UAV target assignment using distributed tour calculation. In: Grundel, D., Murphy, R., Pardalos, P.M. (eds) Theory and Algorithms for Cooperative Systems, Series on Computers and Operations Research, vol. 4, pp. 327–333. Kluwer, Dordrecht (2004)
Dubin, U.: The cross-entropy method for combinatorial optimization with applications. Master’s thesis, The Technion, Israel Institute of Technology, Haifa, June (2002)
Dubin, U.: Application of the cross-entropy method for image segmentation. Ann. Oper. Res. (2004) (submitted)
Pasiliao E.L.: Local neighborhoods for the multidimensional assignment problem. In: Hirsch, M.J., Pardalos, P.M., Murphey, R. (eds) Dynamics of Information Systems, Springer Optimization and its Applications, vol. 40, pp. 353–371. Springer, Berlin (2010)
Krokhmal P., Murphey R., Pardalos P., Uryasev S.: Use of conditional value-at-risk in stochastic programs with poorly defined distributions. In: Butenko, S., Murphey, R., Pardalos, P. (eds) Recent Developments in Cooperative Control and Optimization, pp. 225–242. Kluwer, Dordrecht (2004)
Le Ny, J., Feron, E.: An Approximation Algorithm for the Curvature-Constrained Travelling Salesman Problem. 43rd Annual Allerton Conference on Communications, Control and Computing, Monticello, Sept. (2005)
Murray R.M.: Recent research in cooperative control of multivehicle systems. J. Dyn. Syst. Measure. Control 129(5), 571–583 (2007)
Nygard K.E., Altenburg K., Tang K., Schesvold D.: A decentralized swarm approach to asset patrolling with unmanned air vehicles. In: Grundel, D., Murphy, R., Pardalos, P.M. (eds) Theory and Algorithms for Cooperative Systems, Series on Computers and Operations Research, vol. 4, pp. 327–338. Kluwer, Dordrecht (2004)
Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall, Englewood Cliffs (1982)
Pardalos, P.M., Pitsoulis, L.S. (eds): Nonlinear Assignment Problems: Algorithms and Applications. Combinatorial Optimization, vol. 7. Kluwer, Dordrecht (2000)
Protvin J.Y.: Genetic algorithms for the travelling salesman problem. Ann. Oper. Res. 63(3), 339–370 (1996)
Richards, A., Bellingham, J., Tillerson, M., How, J.P.: Coordination and control of multiple UAVs. AIAA Guidance, Navigation and Control Conference, Monterey, Aug. (2002)
Richards, A., How, J.P.: Aircraft Trajectory Planning With Collision Avoidance Using Mixed Integer Linear Progrmming. American Control Conference, Anchorage, AK, May (2002)
Rubinstein R.Y.: Optimization of cumputer simulation models with rare events. Eur. J. Oper. Res. 99, 89–112 (1997)
Rubinstein R.Y.: The simulated entropy method for combinatorial and continuous optimization. Methodol. Comput. Appl. Probab. 2, 127–190 (1999)
Rubinstein R.Y.: Combinatorial optimization, cross-entropy, ants and rare events. In: Uryasev, S., Pardalos, P.M. (eds) Stochastic Optimization: Algorithms and Application, pp. 304–358. Kluwer, Dordrecht (2001)
Rubinstein R.Y.: The cross-entropy method and rare-events for maximal cut and bipartition problems. ACM Trans. Model. Comput. Simul. 12(1), 27–53 (2002)
Rubinstein R.Y., Kroese D.P.: The Cross-Entropy Method: A Unified Approach to Monte Carlo Simulation. Randomized Optimization and Machine Learning. Springer, Berlin (2004)
Salman A., Ahmad I., Al-Madani S.: Particle swarm optimization for task assignment problem. Microprocess. Microsyst. 26(8), 363–371 (2002)
Schumacher, C., Chandler, P., Pachter, M., Pachter, L.: Constrained Optimization for UAV Task Assignmnet. AIAA Guidance, Navigation, and Control Conference, Providence, Aug. (2004)
Maddula T., Minai A.A., Polycarpou M.: Multi-target assignment and path planning for groups of UAVs. In: Butenko, S., Murphey, R., Pardalos, P. (eds) Cooperative Control and Optimization, pp. 261–272. Kluwer, Dordrecht (2004)
Jin Y., Polycarpou M., Minai A.A.: Cooperative real-time task allocation among groups of UAVs. In: Butenko, S., Murphey, R., Pardalos, P. (eds) Cooperative Control and Optimization, pp. 207–224. Kluwer, Dordrecht (2004)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Le Thi, H.A., Nguyen, D.M. & Pham Dinh, T. Globally solving a nonlinear UAV task assignment problem by stochastic and deterministic optimization approaches. Optim Lett 6, 315–329 (2012). https://doi.org/10.1007/s11590-010-0259-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-010-0259-x