Nous étudions des techniques distribuées de planification sur des scénarios d’observation de la Terre avec utilisateurs et satellites multiples. Nous nous concentrons sur la coordination des utilisateurs ayant réservé des portions d’orbites exclusives et d’un planificateur central ayant plusieurs demandes qui peuvent utiliser certains intervalles de ces portions exclusives. Nous définissons le problème de planification de constellations de satellites d’observation de la Terre (EOSCSP, ou Earth Observation Satellite Constellation Scheduling Problem). Pour le résoudre, nous proposons des schémas multiagents de résolution distribuée, à savoir l’optimisation sous contraintes distribuées et les enchères, dans lesquelles les agents se coordonnent pour répartir les demandes sans partager leurs propres plans. Ces contributions sont évaluées expérimentalement sur des instances EOSCSP générées sur la base de carnets d’observation réels grande échelle ou très conflictuels.
We investigate the use of distributed scheduling techniques on problems related to Earth observation scenarios with multiple users and satellites. We focus on the problem of coordinating users having reserved exclusive orbit portions and one central planner having several requests that may use some intervals of these exclusives. We define this problem as Earth Observation Satellite Constellation Scheduling Problem (EOSCSP) and map it to a Mixed Integer Linear Program. As to solve EOSCSP, we propose multiagent distributed solving schemes, namely Distributed Constraint Optimization and Auctions, where agents coordinate to allocate requests without sharing their own schedules. These contributions are experimentally evaluated on EOSCSP instances based on real large-scale or very conflicting observation order books.
Accepté le :
Publié le :
Keywords: Satellite Constellations, Scheduling, Resource Allocation, Distributed Optimization, Auctions
CC-BY 4.0
@article{ROIA_2023__4_2_147_0,
author = {Gauthier Picard},
title = {Ench\`eres et optimisation multiagent pour la planification de t\^aches d{\textquoteright}observation dans une constellation de satellites},
journal = {Revue Ouverte d'Intelligence Artificielle},
pages = {147--168},
publisher = {Association pour la diffusion de la recherche francophone en intelligence artificielle},
volume = {4},
number = {2},
year = {2023},
doi = {10.5802/roia.60},
language = {fr},
url = {https://roia.centre-mersenne.org/articles/10.5802/roia.60/}
}
TY - JOUR AU - Gauthier Picard TI - Enchères et optimisation multiagent pour la planification de tâches d’observation dans une constellation de satellites JO - Revue Ouverte d'Intelligence Artificielle PY - 2023 SP - 147 EP - 168 VL - 4 IS - 2 PB - Association pour la diffusion de la recherche francophone en intelligence artificielle UR - https://roia.centre-mersenne.org/articles/10.5802/roia.60/ DO - 10.5802/roia.60 LA - fr ID - ROIA_2023__4_2_147_0 ER -
%0 Journal Article %A Gauthier Picard %T Enchères et optimisation multiagent pour la planification de tâches d’observation dans une constellation de satellites %J Revue Ouverte d'Intelligence Artificielle %D 2023 %P 147-168 %V 4 %N 2 %I Association pour la diffusion de la recherche francophone en intelligence artificielle %U https://roia.centre-mersenne.org/articles/10.5802/roia.60/ %R 10.5802/roia.60 %G fr %F ROIA_2023__4_2_147_0
Gauthier Picard. Enchères et optimisation multiagent pour la planification de tâches d’observation dans une constellation de satellites. Revue Ouverte d'Intelligence Artificielle, Volume 4 (2023) no. 2, pp. 147-168. doi : 10.5802/roia.60. https://roia.centre-mersenne.org/articles/10.5802/roia.60/
[1] Optimization-Based Scheduling Method for Agile Earth-Observing Satellite Constellation, Journal of Aerospace Information Systems, Volume 15 (2018) no. 11, pp. 611-626 | DOI
[2] Consensus-Based Decentralized Auctions for Robust Task Allocation, IEEE Trans. Robotics, Volume 25 (2009) no. 4, pp. 912-926 | DOI
[3] Combinatorial Auctions (Peter Cramton; Yoav Shoham; Richard Steinberg, eds.), MIT Press, 2010
[4] Market-Based Multirobot Coordination : A Survey and Analysis, Proceedings of the IEEE, Volume 94 (2006) no. 7, pp. 1257-1270 | DOI
[5] Activity Networks : Project Planning and Control by Network Models, A Wiley-Interscience publication, Wiley, 1977
[6] Decentralised Coordination of Low-power Embedded Devices Using the Max-sum Algorithm, International Conference on Autonomous Agents and Multiagent Systems (AAMAS’08) (2008), pp. 639-646
[7] Distributed Constraint Optimization Problems and Applications : A Survey, Journal of Artificial Intelligence Research, Volume 61 (2018), pp. 623-698 | DOI | MR | Zbl
[8] The Power of Sequential Single-Item Auctions for Agent Coordination, Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA, AAAI Press (2006), pp. 1625-1629 http://www.aaai.org/Library/AAAI/2006/aaai06-266.php
[9] Selecting and scheduling observations of agile satellites, Aerospace Science and Technology, Volume 6 (2002) no. 5, pp. 367 -381 | DOI
[10] Distributed Algorithms for DCOP : A Graphical-Game-Based Approach, Proceedings of the 17th International Conference on Parallel and Distributed Computing Systems (PDCS) (2004), pp. 432-439
[11] ADOPT : Asynchronous distributed constraint optimization with quality guarantees, Artificial Intelligence Journal (2005), pp. 149-180 | DOI | Zbl
[12] A scalable method for multiagent constraint optimization, International Joint Conference on Artificial Intelligence (IJCAI’05) (2005), pp. 266-271
[13] A Case Study on Auction-Based Task Allocation Algorithms in Multi-Satellite Systems, AIAA Scitech 2021 Forum (2021) | DOI
[14] Planification multi-utilisateurs et multi-satellites de tâches d’observation dans des constellations avec portions d’orbites exclusives, Collectifs cyber-physiques - Vingt-neuvièmes Journées Francophones sur les Systèmes Multi-Agents, Bordeaux, France, June 28-30, 2021 (Jean-Paul Jamont, ed.), Cépaduès (2021), pp. 117-126
[15] pyDCOP, a DCOP library for IoT and dynamic systems, International Workshop on Optimisation in Multi-Agent Systems (OptMAS@AAMAS 2019) (2019)
[16] Scheduling the World’s Largest Earth-Observing Fleet of Medium-Resolution Imaging Satellites, IWPSS (2019), pp. 156-161
[17] Satellite Constellations, Journal of the British Interplanetary Society, Volume 37 (1984), 559
[18] Agile Earth observation satellite scheduling over 20 years : formulations, methods and future directions (2020) (https://arxiv.org/abs/2003.06169)
[19] Distributed Stochastic Search and Distributed Breakout : Properties, Comparison and Applications to Constraint Optimization Problems in Sensor Networks, Artificial Intelligence, Volume 161 (2005) no. 1-2, pp. 55-87 | DOI | MR | Zbl
Cité par Sources :