OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

A GA-guided Trial-based Heuristic Tree Search Approach for Multi-Agent Package Delivery Planning

Sata, Bernardo and Lacan, Jérôme and Ponzoni Carvalho Chanel, Caroline A GA-guided Trial-based Heuristic Tree Search Approach for Multi-Agent Package Delivery Planning. (2021) In: Scheduling and Planning Applications Wokrshop (SPARK) at ICAPS, 4 August 2021 (Virtual event, China). (Unpublished)

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


A multitude of planning and scheduling applications have to face constrained time deadlines while proposing appropriate policy solutions under uncertainty. An example of that, is the last mile delivery problem, in which a large fleet of drones needs to be managed in a broad urban area to efficiently deliver packages in response of immediate known requests and future likely requests. This application case can be seen as a sequential decision-making problem under uncertainty asking for a good solution in a constrained time deadline. In this context, this work proposes to approach a delivery policy using a combination of the Trial-based Heuristic Tree Search (THTS) and a Genetic Algorithm (GA). Specifically, during policy search trials, the GA is used as a meta-heuristic function inside the THTS paradigm to suggest the most cost-promising actions concerning drone-request immediate allocation given the current set of requests. Then, the THTS algorithm exploits the GA suggested actions and likely requests arrivals to generate only relevant branches in the tree. It enables to concentrate the search around those actions, breaking-out the inherent combinatorial nature of this planning problem. To evaluate the proposed approach a full size implementation of the aforementioned structure was built for different problem sizes, and compared to a non GA-guided THTS algorithm in order to assess its execution time and expected value performance. The results suggest this simple yet effective approach is a promising venue to fast achieve sub-optimal but reasonable cost solutions.

Item Type:Conference or Workshop Item (Paper)
HAL Id:hal-03336832
Audience (conference):International conference without published proceedings
Uncontrolled Keywords:
Institution:Université de Toulouse > Institut Supérieur de l'Aéronautique et de l'Espace - ISAE-SUPAERO (FRANCE)
Laboratory name:
Deposited On:25 Aug 2021 16:39

Repository Staff Only: item control page