Abstract (EN)

Les Knowledge-Based Programs (KBPs) associent representation des connaissances et pla-nification. Il s'agit de protocoles decrivant les actions a effectuer par un agent, en fonction de son etat de connaissance, afin d'atteindre un but donne. Ces plans possedent une grande expressivite, grâce a l'uti-lisation de la logique modale S5, et une plus grande compacite que les plans classiques. La question de la generation de tels plans n'a ete que peu etudiee. Notre objectif est de combler ce manque. Nous pro-posons des algorithmes permettant de generer des KBPs a partir de la specification d'un etat initial, d'un but et d'un ensemble d'actions disponibles. Deux types d'algorithmes sont presentes, par progression, c'est-a-dire en partant de l'etat initial pour aller vers le but, et par regression, en partant cette fois-ci du but. Dans les deux cas, un algorithme de recherche en largeur est decrit, ayant la propriete de fournir un plan optimal en nombre d'actions a effectuer dans le pire cas. De meme, nous exposons dans les deux cas des algorithmes de recherche en profondeur, dans lesquels une action est choisie pour chaque etat de connaissance, par le biais de differentes fonctions heuristiques dont nous montrons certaines proprietes. Nous proposons egalement des benchmarks adaptes, pour lesquels la planification classique est moins precise, et testons nos algorithmes sur ces problemes.