Dynamic and unstructured multiple cooperative autonomous underwater vehicle (AUV) missions are highly complex operations, and task allocation and path planning are made significantly more challenging under realistic underwater acoustic communication constraints. This paper presents a solution for the task allocation and path planning for multiple AUVs under marginal acoustic communication conditions: a location-aided task allocation framework (LAAF) algorithm for multitarget task assignment and the grid-based multiobjective optimal programming (GMOOP) mathematical model for finding an optimal vehicle command decision given a set of objectives and constraints. Both the LAAF and GMOOP algorithms are well suited in poor acoustic network condition and dynamic environment. Our research is based on an existing mobile ad hoc network underwater acoustic simulator and blind flooding routing protocol. Simulation results demonstrate that the location-aided auction strategy performs significantly better than the well-accepted auction algorithm developed by Bertsekas in terms of task-allocation time and network bandwidth consumption. We also demonstrate that the GMOOP path-planning technique provides an efficient method for executing multiobjective tasks by cooperative agents with limited communication capabilities. This is in contrast to existing multiobjective action selection methods that are limited to networks where constant, reliable communication is assumed to be available. 1. Introduction Autonomous underwater vehicles (AUVs) represent one of the most challenging frontiers for robotics research. AUVs work in an unstructured environment and face unique perception, communication, and control difficulties. Currently, the state of the art in mission planning is dominated by single AUV operations using preplanned trajectories with offline postprocessing of the data collected during the mission. Multiple cooperative vehicle systems (MCVSs) hold great promise for use in large-scale oceanographic surveys, mine countermeasures (MCMs), and other underwater missions, due to better resource and task allocation [1–3]. Simultaneous use of multiple vehicles can improve performance, reduce mission time, and increase the likelihood of mission success. It is not necessary for all the vehicles in an operation to be the same. In fact, heterogeneity could become a powerful driver of multiple AUV (MAUV) operations. Instead of using a single vehicle or a homogeneous fleet able to perform every possible mission, a fleet could comprise a variety of AUVs [4]. Different missions would
References
[1]
R. L. Wernli, “AUVs-a technology whose time has come,” in Proceedings of the International Symposium on Underwater Technology, pp. 309–314, April 2002.
[2]
M. Herman and J. S. Albus, “Overview of the multiple autonomous underwater vehicles (MAUV) project,” in Proceedings of the IEEE International Conference on Robotics and Automation, vol. 1, pp. 618–620, April 1988.
[3]
T. R. Cuff and R. W. Wall, “Support platform and communications to manage cooperative AUV operations (OCEANS '06),” in Proceedings of the Oceans Conference in Asia Pacific, pp. 1–8, May 2007.
[4]
D. Spenneberg, C. Waldmann, and R. Babb, “Exploration of underwater structures with cooperative heterogeneous robots,” in Proceedings of the Oceans '05—Europe, pp. 782–786, June 2005.
[5]
E. M. Sozer, M. Stojanovic, and J. G. Proakis, “Underwater acoustic networks,” IEEE Journal of Oceanic Engineering, vol. 25, no. 1, pp. 72–83, 2000.
[6]
E. H. Turner and R. M. Turner, “A schema-based approach to cooperative problem solving with autonomous underwater vehicles,” in Proceedings of the Ocean Technologies and Opportunities in the Pacific for the 90's (Oceans'91), vol. 2, pp. 1067–1073, October 1991.
[7]
S. M. Smith, K. Ganesan, P. E. An, and S. E. Dunn, “Strategies for simultaneous multiple autonomous underwater vehicle operation and control,” International Journal of Systems Science, vol. 29, no. 10, pp. 1045–1063, 1998.
[8]
D. Stilwell and B. Bishop, “Platoons of underwater vehicles,” IEEE Control Systems Magazine, vol. 20, no. 6, pp. 45–52, 2000.
[9]
F. Arrichiello, D. N. Liu, S. Yerramalli et al., “Effects of underwater communication constraints on the control of marine robot teams,” in Proceedings of the 2nd International Conference on Robot Communication and Coordination, April 2009.
[10]
M. Vajapeyam, S. Vedantam, U. Mitra, J. C. Preisig, and M. Stojanovic, “Distributed space-time cooperative schemes for underwater acoustic communications,” IEEE Journal of Oceanic Engineering, vol. 33, no. 4, pp. 489–501, 2008.
[11]
G. Hollinger, S. Yerramalli, S. Singh, U. Mitra, and G. Sukhatme, “Distributed coordination and data fusion for underwater search,” in Proceedings of the IEEE International Conference on Robotics and Automation (ICRA '11), pp. 349–355, Shanghai, China, May 2011.
[12]
C. Schumacher, P. Chandler, M. Pachter, and L. S. Pachter, “Constrained optimization for UAV task assignment,” in Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 3152–3165, Austin, Tex, USA, 2003.
[13]
R. M. Turner and E. H. Turner, “Simulating an autonomous oceanographic sampling network: a multi-fidelity approach to simulating systems of systems,” in Proceedings of the Oceans '00, pp. 905–911, September 2000.
[14]
H. Bojinov, A. Casal, and T. Hogg, “Emergent structures in modular self-reconfigurable robots,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1734–1741, San Francisco, Calif, USA, April 2000.
[15]
B. Jouvencel, V. Creuze, and P. Baccou, “A new method for multiple AUV coordination a reactive approach,” in Proceedings of the 8th International Conference on Emerging Technologies and Factory Automation (ETFA '01), vol. 1, pp. 51–55, October 2001.
[16]
B. P. Gerkey and M. J. Matari？, “A formal analysis and taxonomy of task allocation in multi-robot systems,” International Journal of Robotics Research, vol. 23, no. 9, pp. 939–954, 2004.
[17]
L. Liu and D. A. Shell, “Multi-level partitioning and distribution of the assignment problem for large-scale multi-robot task allocation,” in Proceedings of the Robotics: Science and Systems Conference (RSS '11), Los Angeles, Calif, USA, June 2011.
[18]
A. Chavez, A. Moukas, and P. Maes, “Challenger: a multi-agent system for distributed resource allocation,” in Proceedings of the 1st International Conference on Autonomous Agents, pp. 323–331, Marina del Rey, Calif, USA, February 1997.
[19]
D. P. Bertsekas, “The auction algorithm: a distributed relaxation method for the assignment problem,” Annals of Operations Research, vol. 14, no. 1, pp. 105–123, 1988.
[20]
S. Sariel and T. R. Balch, “Efficient bids on task allocation for multi-robot exploration,” in Proceedings of the 19th International Florida Artificial Intelligence Research Society Conference (FLAIRS '06), pp. 116–121, May 2006.
[21]
M. J. Matari？, G. S. Sukhatme, and E. H. Ostergaard, “Multi-robot task allocation in uncertain environments,” Autonomous Robots, vol. 14, no. 2-3, pp. 255–263, 2003.
[22]
D. P. Bertsekas, “An Auction Algorithm for Shortest Paths,” webpage: PSU-auction-28, 1991.
[23]
K. E. Nygard, P. R. Chandler, and M. Pachter, “Dynamic network flow optimization models for air vehicle resource allocation,” in Proceedings of the American Control Conference, pp. 1853–1858, Arlington, Va, USA, June 2001.
[24]
J. W. Mitchell, P. Chandler, M. Pachter, and S. J. Rasmussen, “Communication delays in the cooperative control of wide area search munitions via iterative network flow,” in Proceedings of the AIAA Guidance, Navigation, and Control Conference and Exhibit, pp. 2003–5665, Austin, Tex, USA, August 2003.
[25]
E. Carlson, P. Beaujean, and E. An, “Location-aware routing protocol for underwater acoustic networks,” in Proceedings of the MTS/IEEE Oceans ’06, Boston, Mass, USA, September 2006.
[26]
Y. Deng, Task allocation and path planning for acoustic networks of AUVs [Ph.D. thesis], Florida Atlantic University, Boca Raton, Fla, USA, 2010.
[27]
B. Jouvencel, V. Creuze, and P. Baccou, “A new method for multiple AUV coordination a reactive approach,” in Proceedings of the 8th International Conference on Emerging Technologies and Factory Automation (ETFA '01), vol. 1, pp. 51–55, October 2001.
[28]
J. T. Napoli, T. J. Tarn, J. R. Morrow Jr., and E. An, “Optimal communication control for cooperative autonomous underwater vehicle networks,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 1624–1631, Barcelona, Spain, April 2005.
[29]
A. Martins, J. M. Almeida, and E. Silva, “Coordinated maneuver for gradient search using multiple AUVs,” in Proceedings of the Oceans '03, vol. 1, pp. 347–352, September 2003.
[30]
R. Kumar and J. A. Stover, “A behavior-based intelligent control architecture with application to coordination of multiple underwater vehicles,” IEEE Transactions on Systems, Man, and Cybernetics A, vol. 30, no. 6, pp. 767–784, 2000.
[31]
J. Albus and D. Blidberg, “A control system architecture for multiple autonomous undersea vehicles (MAUV),” in Proceedings of the 5th International Symposium on Unmanned Untethered Submersible Technology, vol. 5, pp. 444–466, June 1987.
[32]
J. B. de Sousa and A. Gollu, “Simulation environment for the coordinated operation of multiple autonomous underwater vehicles,” in Proceedings of the Winter Simulation Conference, pp. 1169–1175, December 1997.
[33]
Y. C. Sun and C. C. Cheah, “Coordinated control of multiple cooperative underwater vehicle-manipulator systems holding a common load,” in Proceedings of the MTTS/IEEE TECHNO-Ocean '04, vol. 3, pp. 1542–1547, November 2004.
[34]
M. R. Benjamin, “Multi-objective autonomous vehicle navigation in the presence of cooperative and adversarial moving contacts,” in Proceedings of the Oceans '02 MTS/IEEE, vol. 3, pp. 1878–1885, October 2002.
[35]
M. R. Benjamin, The interval programming: a multi-objective optimization model for autonomous vehicle control [Ph.D. thesis], Brown University, Providence, RI, USA, 2002.
[36]
Y. Deng, P. P. J. Beaujean, E. An, and E. A. Carlson, “A path planning control strategy for search-classify task using multiple cooperative underwater vehicles,” in Proceedings of the MTS/IEEE Oceans ’08, Quebec, Canada, September 2008.
[37]
E. Carlson, P. Beaujean, and E. An, “An Ad Hoc wireless acoustic network simulator applied to multiple underwater vehicle operations in shallow waters using high-frequency acoustic modems,” Journal of Underwater Acoustics, vol. 56, pp. 113–139, 2006.
[38]
H. Kenn and A. Pfeil, “A sound source localization sensor using probabilistic occupancy grid maps,” in Proceedings of the Mechatronics and Robotics Conference, pp. 802–807, 2004.
[39]
B. Yamauchi, A. Schultz, and W. Adams, “Mobile robot exploration and map-building with continuous localization,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 3715–3720, Leuven, Belgium, May 1998.
[40]
H. Moravec and A. Elfes, “High resolution maps from wide angle sonar,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 116–121, St. Louis, Mo, USA, 1985.
[41]
A. M. Law and W. D. Kelton, Simulation Modeling & Analysis, McGraw-Hill, 2nd edition, 1991.
[42]
O. Khatib, “Real-time obstacle avoidance for manipulators and mobile robots,” in Proceedings of the IEEE International Conference on Robotics and Automation, pp. 500–505, St. Louis, Mo, USA, March 1985.
