OPEN ACCESS
Mission planning for a constellation of satellites is a complex problem raising significant technological challenges for tomorrow’s space systems. The large numbers of customers requests and their dynamic introduction result in a huge combinatorial search space. Today’s techniques have several limitations, in particular, it is impossible to dynamically adapt the plan during its construction, and satellites are planned in a chronological way instead of a more collective planning which can provide additional load balancing.
In this paper, we propose to solve this difficult and dynamic problem using adaptive multi-agent systems, taking advantage from their self-adaptation and self-organization mechanisms. Thus, local interactions allow to dynamically reach a good solution. Finally, a comparison with a chronological greedy algorithm, commonly used in the spatial domain, highlights the advantages of the presented system.
adaptive multi-agent system, planning, multi-satellite
Les auteurs souhaitent remercier l’IRT Saint Exupéry pour le financement de cette recherche.
Bensana E., Verfaillie G. (1999). Earth Observation Satellite Management. In Constraints, vol. 299, p. 293–299.
Bensana E., Verfaillie G., Agnese J., Bataille N., Blumstein D. (1996). Exact &inexact methods for daily management of earth observation satellite. In Spaceops’ 96, vol. 394, p. 507.
Bianchessi N., Cordeau J. F., Desrosiers J., Laporte G., Raymond V. (2007, mars). A heuristic for multi-satellite, multi-orbit and multi-user management of Earth observation satellites. European Journal of Operational Research, vol. 177, no 2, p. 750–762.
Boes J., Nigon J., Verstaevel N., Gleizes M.-P., Migeon F. (2015). The Self-Adaptive Context Learning Pattern: Overview and Proposal. In CONTEXT 2015. Cyprus.
Bonjean N., Mefteh W., Gleizes M.-P., Maurel C., Migeon F. (2014). Adelfe 2.0. In Handbook on agent-oriented design processes, p. 19–63.
Bonnet G. (2008). Coopération au sein d’une constellation de satellites. These de Doctorat.
Bonnet G., Tessier C. (2009). Évaluation d’un système multirobot cas d’une constellation de satellites. Revue d’Intelligence Artificielle, vol. 23, p. 565–593.
Bouveret S., Lemaître M. (2006). Un algorithme de programmation par contraintes pour la recherche d’allocations leximin-optimales. In JFPC, 2014.
Bouziat T., Combettes S., Camps V., Glize P. (2014). La criticité comme moteur de la coopération dans les systèmes multi-agents adaptatifs (short paper). In JFSMA, 2014, p. 149–158. Citeseer.
Cordeau J.-F., Laporte G. (2005). Maximizing the value of an earth observation satellite orbit. Journal of the Operational Research Society, vol. 56, no 8, p. 962–968.
Dago P. (1997). Extension d’algorithes dans le cadre des problèmes de satisfaction de contraintes valués. These de Doctorat.
Frank J., Ari J., Morris R., Smith D. E., Field M. (2001). Planning and Scheduling for Fleets of Earth Observing Satellites. In International Symposium on Artificial Intelligence, Robotics, Automation and Space.
Gleizes M.-P. (2012). Self-adaptive Complex Systems (regular paper). In European Workshop on Multi-Agent Systems, Maastricht, The Netherlands, vol. 7541, p. 114–128.
Globus A., Crawford J., Lohn J., Pryor A. (2003). Scheduling earth observing satellites with evolutionary algorithms. In Conference on space mission challenges for information technology.
Globus A., Crawford J., Lohn J., Pryor A. (2004). A comparison of techniques for scheduling earth observing satellites. In Aaai, p. 836–843.
Grasset-Bourdel R., Flipo A., Verfaillie G. (2011). Planning and replanning for a constellation of agile Earth observation satellites. International Conference on Automated Planning and Scheduling.
Jordehi A. R., Jasni J. (2015). Particle swarm optimisation for discrete optimisation problems: a review. Artificial Intelligence Review, vol. 43, no 2, p. 243–258.
Kaddoum E. (2011). Optimization under Constraints of Distributed Complex Problems using Cooperative Self-Organization. These de Doctorat.
Lemaître M., Verfaillie G., Jouhaud F., Lachiver J. M., Bataille N. (2002). Selecting and scheduling observations of agile satellites. In Aerospace Science and Technology vol 6.
Mansour M. A., Dessouky M. M. (2010). A genetic algorithm approach for solving the daily photograph selection problem of the spot5 satellite. Computers & Industrial Engineering, vol. 58, no 3, p. 509–520.
Mavrovouniotis M., Müller F. M., Yang S. (2015). An ant colony optimization based memetic algorithm for the dynamic travelling salesman problem. In Proceedings of the 2015 on genetic and evolutionary computation conference, p. 49–56.
Modi P. J., Shen W.-M., Tambe M., Yokoo M. (2005). Adopt: Asynchronous distributed constraint optimization with quality guarantees. In Artificial Intelligence vol 161.
O Ramos G. de, Rial J. C. B., Bazzan A. L. (2013). Self-adapting coalition formation among electric vehicles in smart grids. In Self-adaptive and self-organizing systems 2013
Tangpattanakul P., Jozefowiez N., Lopez P. (2015). A multi-objective local search heuristic for scheduling earth observations taken by an agile satellite. European Journal of Operational Research, vol. 245, no 2, p. 542–554.
Wang P., Reinelt G., Gao P., Tan Y. (2011). A model, a heuristic and a decision support system to solve the scheduling problem of an earth observing satellite constellation. Computers & Industrial Engineering, vol. 61, no 2, p. 322–335.
Wu G.,Wang H., Li H., PedryczW., Qiu D., Ma M. et al. (2014, janvier). An adaptive Simulated Annealing-based satellite observation scheduling method combined with a dynamic task clustering strategy. Computing Research Repository, vol. abs/1401.6098, p. 23.
Yuan Z., Chen Y., He R. (2014). Agile earth observing satellites mission planning using genetic algorithm based on high quality initial solutions. In IEEE Congress on Evolutionary Computation.