Abstract
This paper addresses a search planning and task allocation problem for a Unmanned Aerial Vehicle (UAV) team that performs a search and destroy mission in an environment where targets with different values move around. The UAVs are heterogeneous having different sensing and attack capabilities, and carry limited amount of munitions. The objective of the mission is to find targets and eliminate them as quickly as possible considering the values of the targets. In this context, there are two distinct issues that need to be addressed simultaneously: search planning and task allocation. The search plan generates an efficient search path for each UAV to facilitate a fast target detection. The task allocation assigns UAVs attack tasks over detected targets such that each UAV’s attack capability is respected. We model these two issues in one framework and propose a distributed approach that utilizes a probabilistic decision making mechanism based on response threshold model. The proposed approach accounts for natural uncertainties in the environment, and provides flexibility, resulting in efficient exploration in the environment and effective allocation of attack tasks. The approach is evaluated in simulation experiments in comparison with other methods, of which results show that our approach outperforms the other methods.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Unmanned Aircraft Systems Roadmap 2005–2030. Office of Secretary of Defense (2005)
Jin, Y., Liao, Y., Minai, A., Polycarpou, M.: Balancing search and target response in cooperative Unmanned Aerial Vehicle (UAV) team. IEEE Trans. Syst. Man Cybern. B Cybern. 36, 571–587 (2006)
Campos, M., Bonabeau, E., Theraulaz, G., Deneubourg, J.-L.: Dynamic scheduling and division of labor in social insects. Adapt. Behav. 8, 83–92 (2001)
Nouyan, S., Ghizzioli, R., Birattari, M., Dorigo, M.: An insect-based algorithm for the dynamic task allocation problem. Künstlich Intell. 4, 25–31 (2005)
Benkoski, S., Monticino, M., Weisinger, J.: A survey of the search theory literature. Nav. Res. Logist. 38, 469–494 (1991)
Stone D.: Theory of Optimal Search, 2nd edn. Operation Research Society of America, Arlington (1989)
Washburn, A.: On a search for a moving target. Nav. Res. Logist. 27, 315–322 (1980)
Brown, S.: Optimal search for a moving target in discrete time and space. Oper. Res. 28, 1275–1289 (1980)
Stewart, T.: Search for a moving target when searcher motion is restricted. Comput. Oper. Res. 6, 129–140 (1979)
Washburn, A.: Search for a moving target: the FAB algorithm. Oper. Res. 31, 739–751 (1983)
Grundel, D.: Searching for a moving target: optimal path panning. In: Proceedings of the IEEE International Conference on Networking, Sensing, and Control, pp. 867–872. Los Alamitos, CA (2005)
Polycarpou, M., Yang, Y., Passino, K.: A cooperative search framework for distributed agents. In: Proceedings of the 2001 IEEE International Symposium on Intelligent Control, pp. 1–6. Mexico City, Mexico (2001)
Sujit, P., Ghose, D.: Search using multiple UAVs with flight time constraints. IEEE Trans. Aerosp. Electron. Syst. 40, 491–508 (2004)
Yang, Y., Minai, A., Polycarpou, M.: Evidential map-building approaches for multi-UAV cooperative search. In: Proceedings of American Control Conference, pp. 116–121. Portland, OR (2005)
Jin, Y., Minai, A., Polycarpou, M.: Cooperative real-time search and task allocation in UAV teams. In: Proceedings of IEEE International Conference on Decision and Control, pp. 7–12. Maui, Hawaii (2003)
Flint, M., Fernandez-Gaucherand, E., Polycarpou, M.: Cooperative control for UAV’s searching risky environments for targets. In: Proceedings of IEEE International Conference on Decision and Control, pp. 3567–3572. Maui, Hawaii (2003)
Yang, Y., Minai, A., Polycarpou, M.: Decentralized cooperative search by networked UAVs in an uncertain environment. In: Proceedings of American Control Conference, pp. 5558–5563. Boston, Massachusetts (2004)
Flint, M., Polycarpou, M., Fernandez-Gaucherand, E.: Cooperative control for multiple autonomous UAV’s searching for targets. In: Proceedings of IEEE International Conference on Decision and Control, pp. 2823–2828. Las Vegas, Nevada (2002)
Sujit, P., Sinha, A., Ghose, D.: Team, game, and negotiation based intelligent autonomous UAV task allocation for wide area application. In: Chahl, J. S., Jain, L. C., Mizutani, A., Sato-Ilic, M. (eds.) Innovations in Intelligent Machines (1), pp. 39–75. Springer-Verlag, Heidelberg (2007)
Passino, K., Polycarpou, M., Jacques, D., Pachter, M., Liu, Y., Yang, Y., Flint, M., Barum, M.: Cooperative control for autonomous air vehicles. In: Cooperative Control and Optimization. Kluwer, Boston (2002)
Vincent, P., Rubin, I.: A framework and analysis for cooperative search using UAV swarms. In: Proceedings of the 19th Annual ACM Symposium on Applied Computing, pp. 79–86. Nicosia, Cyprus (2004)
Jun, M., D’Andrea, R.: Probability map building of uncertain dynamic environments with indistinguishable obstacles. In: Proceedings of American Control Conference, pp. 3417–3422. Denver, Colorado (2003)
Bertuccelli, L., How, J.: Search for dynamic targets with uncertain probability map. In: Proceedings of American Control Conference, pp. 737–742. Minneapolis, Minnesota (2006)
Shumacher, C., Chandler, P., Pachter, M., Pachter, L.: UAV task assignment with timing constraints via mixed-integer linear programming. In: Proceedings of AIAA 3rd the Unmanned Unlimited Systems Conference, pp. 232–252. Chicago, Illinois (2004)
Nygard, K., Chandler, P., Pachter, M.: Dynamic network flow optimization models for air vehicle resource allocation. In: Proceedings of the American Control Conference, pp. 1853–1858. Arlington, Texas (2001)
Shima, T., Rasmussen, S., Sparks, A., Passino, K.: Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms. Comput. Oper. Res. 33, 3252–3269 (2006)
Arslan, G., Wolfe, J., Shamma, J. Speyer, J.: Optimal planning for autonomous air vehicle battle management. In: Proceedings of the IEEE Conference on Decision and Control, pp. 3782–3787. Las Vegas, Nevada (2002)
Shetty, V., Sudit, M., Nagi, R.: Priority-based assignment and routing of a fleet of unmanned combat aerial vehicles. Comput. Oper. Res. 35, 1813–1828 (2008)
Lemaire, T., Alami, R., Lacroix, S.: A distributed task allocation scheme in multi-UAV context. In: Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1157–1162. New Orleans, Louisiana (2004)
Gurfil, P.: Evaluating UAV flock mission performance using Dudek’s taxonomy. In: Proceedings of the American Control Conference, pp. 4679–4684. Portland, Oregon (2005)
Sujit, P., Sinha, A., Ghose, D.: Multiple UAV task allocation using negotiation. In: Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, pp. 471–478. Hakodate, Hokkaido, Japan (2006)
Sujit, P., Beard, R.: Distributed sequential auctions for multiple UAV task allocation. In: Proceedings of the American Control Conference, pp. 3955–3960. New York City, New York (2007)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Kim, MH., Baik, H. & Lee, S. Response Threshold Model Based UAV Search Planning and Task Allocation. J Intell Robot Syst 75, 625–640 (2014). https://doi.org/10.1007/s10846-013-9887-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-013-9887-6