Allocation and Routing of UAVs with Communication Considerations
Unmanned Air Vehicle (UAV) teams are anticipated to provide surveillance support through algorithms, software, and automation. It is desirable to have algorithms that compute effective and efficient routes for multiple UAVs across a variety of missions. These algorithms must be realizable, practical, and account for uncertainties. In surveillance missions, UAVs act as mobile wireless communication nodes in a larger, underlying network consisting of targets where information is to be collected and base stations where information is to be delivered. The role of UAVs in these networks has primarily been to maintain or improve connectivity while undervaluing routing efficiency. Moreover, many current routing strategies for UAVs ignore communication constraints even though neglecting communication can lead to suboptimal tour designs. Generating algorithms for autonomous vehicles that work effectively despite these communication restrictions is key for the future of UAV surveillance missions.
In this work, both current and new routing strategies for UAVS are analyzed to determine how communications impact efficiency of information return. The best routing strategy is shown to be dependent upon distance between requests, UAV bandwidth, UAV velocity, and data size. It was also shown that under certain communication conditions (large-sized data, long distances, and low bandwidth), a new approach on routing is more efficient than typically adopted strategies.
In this work, this new routing formulation is defined based on a simple communication model and a variation of the traditional vehicle routing problem which uses a new minimum delivery latency objective function. The problem is analyzed, and a heuristic solution is motivated and described. Simulation results show that the heuristic algorithm gives near-optimal results in real time, allowing it to be used for large problem sizes, extended to dynamic scenarios, and robust to problem variations and complexities.
This work was supported partially by several Fellowships at the University of Cincinnati for the completion of a Ph.D. The committee for this thesis was chaired by Dr. Kelly Cohen. The fellowships included:
- DAGSI Fellowship (Dayton Area Graduate Studies Institute)
- SFFP (Summer Faculty Fellowship Program)
- NSF Project STEP Fellowship (National Science Foundation Project for Science and Technology Enhancement Program)
Sabo, D. Kingston, and K. Cohen, “A Formulation and Heuristic Approach to Task Allocation and Routing of UAVs under Limited Communication,” Unmanned Systems, World Scientific Pub. Co., Vol. 2, No. 1, Jan. 2014. doi: 10.1142/S2301385014500010.
Sabo, K. Cohen, M. Kumar, D. Kingston, and T. Arnett, “Experimental Validation of the Allocation of UAVs under Communication Restrictions,” 51st AIAA Aerospace Sciences Meeting, Grapevine, TX, Jan. 2013.
Sabo, M. Kumar, K. Cohen, and D. Kingston, “VRP with Minimum Delivery Latency using Linear Programming,” 2012 AIAA Infotech@Aerospace, Garden Grove, CA, June 2012, AIAA-2012-2561.
Sabo and K. Cohen, “Dynamic Allocation of Unmanned Aerial Vehicles with Communication Constraints,” 2012 AIAA Infotech@Aerospace, Garden Grove, CA, June 2012, AIAA-2012-2455.
Sabo and K. Cohen, “SMART Heuristic for Pickup and Delivery Problem with Cooperative UAVs,” 2011 AIAA Infotech@Aerospace, St. Louis, MO, Mar. 2011, AIAA-2011-1464.
Sabo, D. Kingston, and K. Cohen, “Minimum Service Time for UAV Cooperative Control Subject to Communication Constraints,” 2010 AIAA Infotech@Aerospace, Atlanta, GA, Apr. 2010, AIAA-2010-3344.