Local and Global Phenomena in Dynamic Geographic Resource Allocation
Abstract
The purpose of this project is to apply tools from computational geometry, mathematical optimization, and geometric probability theory to find new algorithms for optimally allocating geographic resources such as supply depots, service facilities, vehicles, backbone networks, or districts of a territory. One of the fundamental concerns in the analysis of geographic problems of this type is the trade-off between localized, decentralized, independent execution of tasks versus execution that is facilitated with a centralized backbone network infrastructure. This is particularly true for problems that have an online or dynamic component in which the problem parameters change over time as new information is collected; a decentralized approach usually requires less initial administrative overhead and may be cheaper in the short term, but a centralized approach will likely be more efficient in the long run. Geographically speaking, service executed at a local level features the obvious benefits of proximity and specialization, inasmuch as strategic targets are visited by agents that are close to them. Conversely, by aggregating network flows via a backbone network, one is able to reap the benefits of economies of scale, economies of agglomeration, and economies of density. This issue is made manifest in the following prototypical questions that one might ask: “Should I visit my targets using a ’peddling’ route that visits multiple destinations, or should I make direct trips from my origin to each of my destinations?” “Given a limited budget, is it better for me to construct more vehicle depots, to buy more vehicles, or augment the capacities of my existing vehicles?” “Should I wait and collect more data regarding the distribution of likely targets before taking action, or should I dispatch my vehicles now?” This project will extend and generalize our results from the previous ONR project #N000141210719, “Online and decentralized algorithms for map segmentation problems”. The primary application of our proposed partitioning algorithms is in designing control policies for routing and locating unmanned aerial vehicles (UAVs), micro air vehicles (MAVs), unmanned undersea vehicles (UUVs), or wireless sensors in a service region. We have identified several exciting new problems in which we will apply the geometric tools developed in our previous project to solve new problems directly relevant to the ONR.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 12, 2016
- Source ID
- N000141512794
Entities
People
- John Gunnar Carlsson
Organizations
- Office of Naval Research
- United States Navy
- University of Southern California