World Scientific
  • Search
  •   
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

An Efficient Genetic Fuzzy Approach to UAV Swarm Routing

    https://doi.org/10.1142/S2301385016500011Cited by:32 (Source: Crossref)

    Fuzzy logic is used in a variety of applications because of its universal approximator attribute and nonlinear characteristics. But, it takes a lot of trial and error to come up with a set of membership functions and rule-base that will effectively work for a specific application. This process could be simplified by using a heuristic search algorithm like Genetic Algorithm (GA). In this paper, genetic fuzzy is applied to the task assignment for cooperating Unmanned Aerial Vehicles (UAVs) classified as the Polygon Visiting Multiple Traveling Salesman Problem (PVMTSP). The PVMTSP finds a lot of applications including UAV swarm routing. We propose a method of genetic fuzzy clustering that would be specific to PVMTSP problems and hence more efficient compared to k-means and c-means clustering. We developed two different algorithms using genetic fuzzy. One evaluates the distance covered by each UAV to cluster the search-space and the other uses a cost function that approximates the distance covered thus resulting in a reduced computational time. We compare these two approaches to each other as well as to an already benchmarked fuzzy clustering algorithm which is the current state-of-the-art. We also discuss how well our algorithm scales for increasing number of targets. The results are compared for small and large polygon sizes.

    This paper was recommended for publication in its revised form by editorial board member, Jun Xu.

    References

    • 1. A. W. Vick, Genetic fuzzy controller for a gas turbine fuel system, Ph.D. thesis, University of Cincinnati (2010). Google Scholar
    • 2. A. Walker, K. Cohen and P. Putman, Fuzzy logic attitude control of a magnetically actuated cubesat, Proc. of the AIAA Infotech @ Aerospace Conference No. AIAA-2013-5059 (AIAA, Boston, MA, 2013). Google Scholar
    • 3. N. Ernest, K. Cohen and C. Schumacher, UAV swarm routing through genetic fuzzy learning methods, Proc. of the AIAA Infotech @ Aerospace Conference No. AIAA-2013-4730 (AIAA, Boston, MA, 2013). Google Scholar
    • 4. N. Ernest, K. Cohen and C. Schumacher, Collaborative tasking of UAVs using a genetic fuzzy approach, Proc. of the 51st Aerospace Sciences Meeting No. AIAA-2013-1032 (Grapevine, TX, 2013). Google Scholar
    • 5. K. J. Obermeyer, Visibility problems for sensor networks and unmanned air vehicles, Ph.D. thesis, University of California Santa Barbara (2010). Google Scholar
    • 6. S. Lin and B. W. Kernighan, An effective heuristic algorithm for the traveling-salesman problem, Oper. Res. 21 (2) (1973) 498–516. CrossrefGoogle Scholar
    • 7. M. Albayrak and N. Allahverdi, Development of a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms, Expert Syst. Appl. 38 (3) (2011) 1313–1320. CrossrefGoogle Scholar
    • 8. S.-M. Chen and C.-Y. Chien, Parallelized genetic ant colony systems for solving the traveling salesman problem, Expert Syst. Appl. 38 (4) (2011) 3873–3883. CrossrefGoogle Scholar
    • 9. Y. Nagata and D. Soler, A new genetic algorithm for the asymmetric traveling salesman problem, Expert Syst. Appl. 39 (10) (2012) 8947–8953. CrossrefGoogle Scholar
    • 10. Y. Nagata, Edge assembly crossover: A high-power genetic algorithm for the traveling salesman problem, Proc. 7th ICGA (1997), pp. 450–457. Google Scholar
    • 11. A. Sathyan, N. Boone and K. Cohen, Comparison of approximate approaches to solving the travelling salesman problem & its application to UAV swarming, Int. J. Unmanned Syst. Eng. 3 (1) (2015) 1–16. CrossrefGoogle Scholar
    • 12. B. L. Golden, G. Laporte and É. D. Taillard, An adaptive memory heuristic for a class of vehicle routing problems with minmax objective, Comput. Oper. Res. 24 (5) (1997) 445–452. CrossrefGoogle Scholar
    • 13. N. Christofides, A. Mingozzi and P. Toth, Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations, Math. Program. 20 (1) (1981) 255–282. CrossrefGoogle Scholar
    • 14. E. Kivelevitch, K. Cohen and M. Kumar, Market-based solution to the allocation of tasks to agents, Procedia Comput. Sci. 6 (2011) 28–33. CrossrefGoogle Scholar
    • 15. E. Kivelevitch, K. Cohen and M. Kumar, On the scalability of the market-based solution to the multiple traveling salesmen problem, Proc. 2012 AIAA Infotech @ Aerospace Conf. No. 2012-2543 (Garden Grove, CA, 2012). Google Scholar
    • 16. S. M. Mitchell, N. D. Ernest and K. Cohen, Comparison of fuzzy optimization and genetic fuzzy methods in solving a modified traveling salesman problem, AIAA Infotech @ Aerospace Conf. No. 2013-4664 (Boston, MA, 2013). Google Scholar
    • 17. N. Ernest and K. Cohen, Fuzzy clustering based genetic algorithm for the multi-depot polygon visiting dubins multiple traveling salesman problem, Proc. 2012 IAAA Infotech @ Aerospace No. AIAA 2012-2562 (AIAA, Garden Grove, CA, 2012). Google Scholar
    • 18. C. Sabo, D. Kingston and K. Cohen, A formulation and heuristic approach to task allocation and routing of uavs under limited communication, Unmanned Syst. 2 (1) (2014) 1–17. LinkGoogle Scholar
    • 19. R. Hosseini, S. D. Qanadli, S. Barman, M. Mazinani, T. Ellis and J. Dehmeshki, An automatic approach for learning and tuning gaussian interval type-2 fuzzy membership functions applied to lung cad classification system, IEEE Trans. Fuzzy Syst. 20 (2) (2012) 224–234. CrossrefGoogle Scholar
    • 20. O. Cordón and O. F. Herrera, A general study on genetic fuzzy systems, Genetic Algorithms in Engineering and Computer Science (Periaux, J.,Winte, G., Eds.), (JohnWiley and Sons, 1995), pp. 33–57. Google Scholar
    • 21. H. Surmann, A. Kanstein and K. Goser, Self-organizing and genetic algorithms for an automatic design of fuzzy control and decision systems, Proc. EUFIT’93 (Citeseer, 1993). Google Scholar
    • 22. M. A. Lee, On genetic representation of high dimensional fuzzy systems, Uncertainty Modeling and Analysis, 1995, and Annual Conf. North American Fuzzy Information Processing Society. Proc. ISUMA-NAFIPS’95, Third Int. Symp. (IEEE, 1995), pp. 752–757. Google Scholar
    • 23. A. Sathyan, N. Ernest and K. Cohen, Genetic fuzzy approach for control and task planning applications, AIAA Infotech @ Aerospace Conference No. AIAA-2015-0887 (AIAA, Kissimmee, FL, 2015). Google Scholar
    • 24. J. Beardwood, J. H. Halton and J. M. Hammersley, The shortest path through many points, Math. Proc. Cambridge Philos. Soc. 55 (4) (1959) 299–327. CrossrefGoogle Scholar
    • 25. M. A. Figliozzi, Planning approximations to the average length of vehicle routing problems with varying customer demands and routing constraints, Transp. Res. Record: J. Transp. Res. Board 2089 (1) (2008) 1–8. CrossrefGoogle Scholar
    • 26. N. Boone, A. Sathyan and K. Cohen, Enhanced approaches to solving the multiple traveling salesman problem, AIAA Infotech @ Aerospace Conference No. AIAA-2015-0889 (AIAA, Kissimmee, FL, 2015). Google Scholar