2 distinctions pour le LAAS à la conférence CP 2012

26 novembre 2012

Des chercheurs du LAAS ont obtenu les prix « Best Application Paper » et « Honorable Mention » lors de la 18e conférence internationale de programmation par contraintes (CP 2012, 8 au 12 oct., Québec, Canada).

• Des chercheurs du LAAS collaborent avec le CNES à l’optimisation des opérations scientifiques prévues pour l'étude du noyau d’une comète par la sonde spatiale Rosetta

Prix "Best Application Paper" - Article "Scheduling Scientific Experiments on the Rosetta/Philae Mission", Gilles Simonin, Christian Artigues, Emmanuel Hébrard, Pierre Lopez.

La mission spatiale Rosetta/Philae, lancée en 2004 par l'Agence Spatiale Européenne, a pour but de rejoindre la comète 67P/Churyumov-Gerasimenko en 2014, de l’observer depuis l’orbite et de se poser sur son noyau afin de l’étudier. Les expérimentations scientifiques sur le sol de la comète génèrent de multiples activités dont l'ordonnancement est un véritable enjeu en regard des contraintes physiques et des ressources matérielles. Les principales contraintes proviennent de différentes limitations portant sur l'énergie fournie par les batteries, la température ambiante dans un compartiment, ou encore les ressources mémoire allouées aux expériences et à l'atterrisseur. En raison de faibles capacités de calcul à bord, les plans d'expériences sont élaborés au sol, puis transmis à la sonde.

Les chercheurs du LAAS-CNRS, s'inscrivant dans le paradigme de la Programmation Par Contraintes, ont proposé des algorithmes résolvant des parties spécifiques du problème global, notamment celui de la gestion du transfert de données sans perte. Ces algorithmes permettront aux ingénieurs du Centre de Navigation et d'Opérations Scientifiques (SONC) du CNES travaillant sur la planification des activités, de produire plus rapidement des plans réalisables, voire optimaux, et respectant au mieux les attentes des scientifiques impliqués dans les expériences. Or, en raison d'incertitudes liées à la méconnaissance a priori de certaines données, en particulier le lieu exact et l’état de l’atterrisseur Philae après l’atterrissage, le plan d'opérations scientifiques définitif doit pouvoir être recalculé au dernier moment dans un temps extrêmement court. L'augmentation de performance obtenue est ainsi déterminante pour une réussite totale du projet.

• Article "An optimal Arc-Consistency Algorithm for a Chain of Atmost Constraints with Cardinality" de Mohamed Siala, Emmanuel Hébrard et Marie-José Huguet

Prix "Honorable Mention".

Résumé de l'article

Dans de nombreuses applications, il y a des restrictions sur les successions de décisions qui peuvent être prises. Certaines séquences sont autorisées ou préférées tandis que d'autres sont interdites. Par exemple, dans les applications de confection d’horaires pour des équipes de salariés, il est souvent demandé de ne pas enchainer un travail de nuit avec un travail du matin pour la même équipe. Plusieurs contraintes de séquencement ont été proposées dans la littérature pour gérer ce type de problèmes.

Dans ce travail, on a pu proposer une nouvelle contrainte globale (noté ATMOSTSEQCARD) traitant un cas particulier de séquencement. Cette contrainte, appliquée à n variables [X1, … Xn], et un ensemble de valeur {V1,..Vk} garantit que dans toute sous-séquence de longueur q, il y a au plus u valeurs de V et que sur l’ensemble de la séquence il y a exactement d apparitions de ces valeurs. Cette contrainte s’applique typiquement aux problèmes d’ordonnancement de véhicules dans des ateliers de fabrication automobile mais aussi à une classe particulière de problèmes de confection d’horaires.

L’apport de l’article se résume par la proposition d’un algorithme de filtrage complet pour la contrainte ATMOSTSEQCARD avec une complexité linéaire (et donc optimal), alors que la meilleure méthode précédente est quadratique. Les résultats expérimentaux montrent l’efficacité de cet algorithme.