Repousser les Limites: Abstraction, Raffinement, et Bornes de Qualité – BARQ

Les problèmes de recherche combinatoire sont présents dans de nombreux
domaines de l'informatique. Une technique commune pour les traiter est
d'exploiter des minorants: des estimations optimistes du coût de la
transformation d'un état en une solution. Mais comment calculer de
telles estimations ? Le projet BARQ qui est proposé attaque cette
question d'une façon très interdisciplinaire incluant la planification
classique, la planification probabiliste, l'ordonnancement, et le
model checking. A notre connaissance, BARQ est le premier projet
abordant tous ces domaines à l'unison. Nous utilisons l'abstraction
pour obtenir des minorants, et nous utilisons le raffinement
d'abstraction pour améliorer incrémentalement ces minorants. Combiné
avec des méthodes de majoration, cela fournit des algorithmes anytimes
très pratiques qui garantissent des bornes sur la qualité de la
solution courante.

La technique principale sur laquelle nous nous focalisons est
l'abstraction d'état, laquelle impose une relation d'équivalence sur
les états. Nous considérons un cadre récent, l'agrégation d'états
emboîtée (NSA pour "nested state aggregation"), pour la construction
de telles abstractions. NSA incorpore une astuce de calcul permettant
une conception affinée de la relation d'équivalence en sélectionnant
des paires d'états à agréger en un seul. Il a été démontré en
planification classique que, en théorie, cette approche domine la
plupart des techniques d'abstraction connues. Ce pouvoir dépend
toutefois de la sélection parfaite des états à agréger. On ne sait à
peu près rien de la façon de faire cette sélection. BARQ comble cette
lacune. Dans ce but, nous nous appuyons sur la recherche en
planification probabiliste et en model checking, lesquels sont
concernés par l'abstraction d'état et le raffinement
d'abstraction. Ces traditions ont abordé des questions similaires,
mais pour des raisons très différentes forçant l'abstraction à
préserver l'ensemble exact de solutions. Notre recherche relâche cette
contrainte pour obtenir des méthodes de minoration à la place,
laissant ainsi apparaître plusieurs nouvelles connexions entre les
domaines abordés.

BARQ est principalement motivé par des questions de recherche
fondamentales. Toutefois, chacun des quatre domaines abordés a une
traduction d'applications pratiques sur lesquelles nous nous
appuierons pour l'évaluation finale des techniques développées.