Abstract
Path planning refers to the generation of a space path between an initial location and the desired destination, with an optimal or near-optimal performance under specific constraints [1]. A path planning algorithm may produce different candidate plans, which should be compared and evaluated based on specific criteria. Such criteria are generally related to feasibility and optimality of the path generation. The first criterion relates to derivation of a plan that moves safely a UAV (an object) to its final state, without taking into account the quality of the produced plan. The second criterion refers to derivation of optimal, yet feasible, paths, with optimality defined according to the problem under consideration [2]. However, searching for optimal paths is not a trivial task; in most cases this requires excessive computational time; in some cases even computation of just one feasible path is a rather involved task. Therefore, the search focuses mostly on suboptimal or just feasible solutions.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Gilmore J. F., “Autonomous vehicle planning analysis methodology”, Proceedings, Association of Unmanned Vehicles Systems Conference, 503–509, 1991.
LaValle S. M, Planning Algorithms, Cambridge University Press, 2006.
Bortoff S., “Path planning for UAVs”, Proceedings, American Control Conference, 364–368, 2000.
Szczerba R. J., Galkowski P., Glickstein I. S., and Ternullo N., “Robust Algorithm for Real-time Route Planning”, IEEE Transactions on Aerospace Electronic Systems, 36, 869–878, 2000.
Zheng C, Li L., Xu F., Sun F., Ding M, “Evolutionary Route Planner for Unmanned Air Vehicles”, IEEE Transactions on Robotics, 21, 609–620, 2005.
Uny Cao Y., Fukunaga A. S., Kahng A. B., “Cooperative Mobile Robotics: Antecedents and Directions”, Autonomous Robots, 4, 7–27, 1997.
Schumacher C, “Ground Moving Target Engagement by Cooperative UAVs”, Proceedings, American Control Conference, Oregon, June 2005.
Mettler B., Schouwenaars T., How J., Paunicka J., and Feron E., “Autonomous UAV Guidance Build-up: Flight-test Demonstration and Evaluation Plan”, Proceedings of the AIAA Guidance, Navigation, and Control Conference, 2003.
Beard R. W., McLain T. W., Goodrich M. A., Anderson E. P., “Coordinated Target Assignment and Intercept for Unmanned Air Vehicles”, IEEE Transactions on Robotics and Automation, 18, 911–922, 2002.
Richards A., Bellingham J., Tillerson M., and How J., “Coordination and Control of UAVs”, Proceedings of the AIAA Guidance, Navigation and Control Conference, Monterey, CA, 2002.
Schouwenaars T., How J., and Feron E., “Decentralized Cooperative Trajectory Planning of Multiple Aircraft with Hard Safety Guarantees”, Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit, 2004.
Flint M., Polycarpou M., and Fernandez-Gaucherand E., “Cooperative Contiol for Multiple Autonomous UAV’s Searching for Targets”, Proceedings, 41 st IEEE Conference on Decision and Control, 2002.
Tang Z., and Ozguner U., “Motion Planning for Multi-Target Surveillance with Mobile Sensor Agents”, IEEE Transactions on Robotics, 21, 898–908, 2005.
Gomez Ortega J., and Camacho E. F., “Mobile Robot Navigation in a Partially Structured Static Environment, Using Neural Predictive Control”, Control Engineering Practice, 4, 1669–1679, 1996.
Kwon Y. D., and Lee J. S., “Online Evolutionary Optimization of Fuzzy Control System Based on Decentralized Population”, Intelligent Automation and Soft Computing, 6, 135–146, 2000.
Nikolos I. K., Valavanis K. P., Tsourveloudis N. C, Kostaras A., “Evolutionary Algorithm Based Offline / Online Path Planner for UAV Navigation”, IEEE Transactions on Systems, Man, and Cybernetics Part B, 33, 898–912, 2003.
Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, Springer, 1999.
Smierzchalski R., “Evolutionary Trajectory Planning of Ships in Navigation Traffic Areas”, Journal of Marine Science and Technology, 4, 1–6, 1999.
Smierzchalski R., and Michalewicz Z., “Modeling of Ship Trajectory in Collision Situations by an Evolutionary Algorithm”, IEEE Transactions on Evolutionary Computation, 4, 227–241, 2000.
Sugihara K., and Smith J., “Genetic Algorithms for Adaptive Motion Planning of an Autonomous Mobile Robot”, Proceedings, IEEE International Symposium on Computational Intelligence in Robotics and Automation, Monterey, California, 138–143, 1997.
Sugihara K., and Yuh J., GA-Based Motion Planning for Underwater Robotic Vehicles, UUST-10, Durham, NH, 1997.
Shima T., Rasmussen S. J., Sparks A. G., “UAV Cooperative Multiple Task Assignments Using Genetic Algorithms”, Proceedings, American Control Conference, Oregon, June 2005.
Moitra A., Mattheyses R. M., Hoebel L. J., Szczerba R. J., Yamrom B., “Multivehicle Reconnaissance Route and Sensor Planning”, IEEE Transactions on Aerospace and Electronic Systems, 37, 799–812, 2003.
Dubins L., “On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Position”, American Journal of Mathematics, 79, 497–516, 1957.
Shima T., Schumacher C, “Assignment of Cooperating UAVs to Simultaneous Tasks Using Genetic Algorithms”, Proceedings, AIAA Guidance, Navigation, and Control Conference and Exhibit, California, 2005.
Martinez-Alfaro H., and Gomez-Garcia S., “Mobile Robot Path Planning and Tracking Using Simulated Annealing and Fuzzy Logic Contiol”, Expert Systems with Applications, 15, 421–429, 1988.
Nikolos I. K., Tsourveloudis N. C, and Valavanis K. P., “Evolutionary Algorithm Based 3-D Path Planner for UAV Navigation”, CD-ROM Proceedings, 9 th Mediterranean Conference on Control and Automation, Dubrovnik, Croatia, 2001.
Piegl L., Tiller W., The NURBS Book, Springer, 1997.
Farin G., Curves and Surfaces for Computer Aided Geometric Design, A Practical Guide, Academic Press, 1988.
Storn R., and Price, K., DE A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Space, ICSI, Technical Report TR-95012, 1995.
Price K. V., Storn R. M, Lampinen J. A., Differential Evolution, a Practical Approach to Global Optimization, Springer, 2005.
Hui-Yuan F., Lampinen J., Dulikravich G. S., “Improvements to Mutation Donor Formulation of Differential Evolution”, Proceedings of EUROGEN Conference on Evolutionary Methods for Design, Optimization and Control, Applications to Industrial and Societal Problems, CIMNE, Barcelona, 2003.
Marse K. and Roberts S. D., “Implementing a portable FORTRAN Uniform (0, 1) Generator”, Simulation, 41–135, 1983.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer. Printed in the Netherlands
About this chapter
Cite this chapter
Nikolos, I.K., Tsourveloudis, N.C., Valavanis, K.P. (2007). Evolutionary Algorithm Based Path Planning for Multiple UAV Cooperation. In: Valavanis, K.P. (eds) Advances in Unmanned Aerial Vehicles. Intelligent Systems, Control and Automation: Science and Engineering, vol 33. Springer, Dordrecht. https://doi.org/10.1007/978-1-4020-6114-1_10
Download citation
DOI: https://doi.org/10.1007/978-1-4020-6114-1_10
Publisher Name: Springer, Dordrecht
Print ISBN: 978-1-4020-6113-4
Online ISBN: 978-1-4020-6114-1
eBook Packages: EngineeringEngineering (R0)