CS SEMINAR

Drone Systems for Delivery of Goods

Speaker
Pasquale Grippa
Research Associate and Teaching Assistant
Alpen-Adria-Universitat Klagenfurt, Austria

Chaired by
Dr LOW Kian Hsiang, Associate Professor, School of Computing
lowkh@comp.nus.edu.sg

13 Jun 2016 Monday, 10:00 AM to 12:00 PM

Executive Classroom, COM2-04-02

Abstract:

We consider a fleet of drones delivering goods to customers scattered on a certain service area. Customers (jobs) arrive according to a space-temporal stochastic process, and vehicles autonomously decide which customer to serve (job selection) in order to optimize some performance metrics (delivery time or profit per delivery). We address two complementary problems in these systems: 1) Dimensioning the system, i.e. choosing the right number of depots and vehicles, and 2) computing policies to control the vehicles. An incorrect dimensioning may prevent to achieve a certain level of service, or may lead to instability (customers waiting forever). An ineffective job selection policy may considerably decrease the performance. To address the first problem, we analyze the performance of two classes of job section policies "first job first" and "nearest job first". We show that the choice of the best policy depends on the operating conditions and on the timing of job selection. Furthermore, we compute a lower bound to the cost necessary to have a certain delivery time. Based on these results, we introduce a method to dimension the system and balance the trade-off between infrastructure expenditure and service level. To address the second problem, we introduce a novel semi-Markov model that enables the computation of optimal policies. The complexity related to the exact modeling makes the computation of the optimal policy unfeasible for real scenarios. To overcome this problem we introduce an approximation method leading to near-optimal performance and applicable in real scenarios.


Biodata:

Pasquale Grippa is a research associate and teaching assistant at Alpen-Adria-Universitat Klagenfurt, Austria. He received his BSc and MSc degrees in electronics engineering from the University of Salerno in 2007 and 2011, respectively. During his studies he was a guest student at the Technical University of Berlin and a research assistant at the Fraunhofer Heinrich Hertz Institute. His research interests include Markov decision processes, (approximate) dynamic programming, multi agent systems, and queuing theory. His research focus is on decision making and task allocation in multi UAV systems with application in logistics.