Pour commencer

En installant SDM'Studio vous avez installer quatre types de fichiers (binaries, headers, documentation et libraries). Par défault, ceux-ci sont situés dans les répertoires suivants:

binaries : /usr/local/bin/
headers : /usr/local/include/
libraries : /usr/local/lib/
documentation : /usr/local/share/

Interface en Ligne de Commande (CLI)

Le programme principal est sdms. Ce programme concentre les différentes fonctionnalités du logiciel. Pour commencer, exécutez les trois commandes ci-dessous:

sdms solve -a "A*" -f "OccupancyMDP" 
sdms solve -a "HSVI" -f "OccupancyMDP" 
sdms solve -a "QLearning" -f "OccupancyMDP" -m 1 -e 0.1 -t 10000

Vous venez de résoudre un POMDP décentralisé grâce à trois algorithmes différents (A*, HSVI et Q-Learning). Le paramètre -f spécifie au programme d'utiliser la reformulation en occupancy MDP pour le résoudre. Pour voir comment utiliser le programme sdms, il faut utiliser sdms --help ou encore man sdms.

    Usage : sdms COMMAND

    The best solver for sequential decision making problems.

    Commands:
      algorithms	Display all available algorithms.
      help			Show this help message.
      solve			Solve a sequential decision making problem using specified algorithm.
      test			Test a policy.
      version		Show the version.
      worlds		Display all available worlds.

    Run 'sdms COMMAND --help' for more information on a command.

Le programme principal sdms contient des alias vers d'autres programmes. Par exemple, la commande sdms solve est équivalent à sdms-solve. Les deux lignes ci-dessous vont retourner exactement la même chose.

sdms solve --help
sdms-solve --help

Formulation d'un problème

Les fichiers de problème peuvent prendre différentes formes. La forme la plus classique est le format .pomdp de Anthony Cassandra. Celui-ci est décrit dans le fichier tiger.dpomdp. On considèrera aussi les formats .dpomdp et .posg comme étant les extensions triviales du format précédent. Quelques fichiers problèmes pré-existants sont situés dans le répertoire /usr/local/share/sdms/world/.

Démarrer avec la bibliothèque SDMS

Pour un ensemble d'exemples, veuillez vous référer à ce dossier (opens new window).

Écrivons un petit fichier C++ appelé backinduct.cpp qui inclut sdm/parser/parser.hpp et qui, pour l'instant, affiche simplement un problème :

#include <iostream>
#include <sdm/config.hpp>
#include <sdm/parser/parser.hpp>

int main() {
  auto problem = sdm::parser::parse_file(sdm::config::PROBLEM_PATH + "dpomdp/mabc.dpomdp");
  std::cout << *problem << std::endl;
}

Définir un problème transformé

Maintenant que nous avons configuré l'environnement de base, nous pouvons nous plonger sur une partie beaucoup plus intéressante. Tout d'abord, nous allons voir comment transformer le problème original en un problème qui peut être résolu par des algorithmes de programmation dynamique. Ensuite, nous montrerons comment définir une reformulation personnalisée du problème et le résoudre avec des algorithmes existants.

Utilisation d'une reformulation existante du problème

Considérons que nous cherchons un moyen de résoudre un POMDP avec les algorithmes de base pour MDPs. A cette effet, définissons une reformulation du POMDP original appelée "belief MDP".

std::shared_ptr<POMDPInterface> pomdp = sdm::parser::parse_file(sdm::config::PROBLEM_PATH + "dpomdp/mabc.dpomdp") ;
std::shared_ptr<BeliefMDP> belief_mdp = std::make_shared<BeliefMDP>(pomdp) ;

Cette reformulation suppose que la transition d'état se fait sur les croyances au lieu des états. Le principal avantage de l'utilisation de cette relaxation est que les algorithmes standards pour les MDP peuvent maintenant être appliqués. L'exemple complet du code est ci-dessous :

#include <iostream>

#include <sdm/config.hpp>
#include <sdm/parser/parser.hpp>
#include <sdm/world/belief_mdp.hpp>
#include <sdm/algorithms/planning/backward_induction.hpp>

using namespace sdm;

int main()
{
    // Parse the problem file
    auto pomdp = sdm::parser::parse_file(sdm::config::PROBLEM_PATH + "dpomdp/tiger.dpomdp");
    pomdp->setHorizon(4);
    // Recast the problem instance into a solvable interface
    auto belief_mdp = std::make_shared<BeliefMDP>(pomdp);
    // Instanciate the algorithm
    auto algo = std::make_shared<BackwardInduction>(belief_mdp);
    // Initialize and solve
    algo->initialize();
    algo->solve();
}

Ajouter une classe de problème

Etape 1: Définir une nouvelle classe de problème

Nous considérerons ici le cas du NDPOMDP (Networked Distributed POMDP). Ceux-ci sont des MPOMDPs où chaque agent dispose de sa propre fonction de transition et d'observation et son propre espace d'états. Par ailleurs, la dynamique des états non contrôlables permet de décrire des phénomènes qui ne sont pas liés à la prise de décision des agents. Enfin, la fonction de récompense est additive par sous-groupe d'agents. En d'autres termes, il existe une fonction de récompense par sous-groupe d'agents, où le nombre de sous-groupe est prédéfini à l'avance.

Etape 2 : Définir la transformation du problème

Cette deuxième étape consiste à définir une reformulation du ND-POMDP en ND-OccupancyMDP. Cette reformulation a pour objectif de résoudre la version décentralisée du problème grâce à des algorithmes de l'état de l'art.

Etape 2.1: Définir la notion d'état d'occupation

La notion d'état dans le cas NDPOMDP est définit comme un tuple d'états d'occupation. Un état d'occupation pour un agent donné est la distribution conditionnelle sur les croyances privées de l'agent sachant la politique poursuivie jusqu'ici par l'agent et sa croyance initiale $\mathbf{\xi}_t = \left(p\left( b^i_t \mid b^i_0, d^i_{0..t} \right)\right)_{i=1..n}$ .

Concrètement, il s'agit ici de créer une classe qui hérite de State et qui permet de représenter la statistique suffisante $\mathbf{\xi}_t$ .

Etape 2.2: Définir la notion d'action

La notion d'action dans le cas NDPOMDP est un tuple de règles de décisions (1 par agent). Une règle de décision dans le contexte NDPOMDP est une fonction qui associe une croyance accessible à l'ensemble des actions de l'agent.

Pour ce cas, on peut directement utiliser la classe DeterministicDecisionRule.

Etape 2.3: Définir la dynamique

La transition d'un état d'occupation à un autre est défini par l'ensemble des transitions sur les états d'occupations individuels.

Etape 2.4: Définir la récompense

La récompense est l'espérance conditionné par le tuple des états d'occupations du groupe.

$r_{xu} = \sum_{g \in G} r_{x^0, x^g, u^g}$ où $g \subseteq \{1,.., n\}$ et $x^g = (x^i)_{i \in g}$ .

Pour définir la dynamique et la récompense, on déclarera une nouvelle classe d'occupancy MDP qui réimplémente les fonctions computeExactNextState et getReward:

#pragma once

#include <sdm/world/occupancy_mdp.hpp>

namespace sdm
{
    class NDOccupancyMDP : public BaseOccupancyMDP<JointBelief>
    {
    public:
        /**
         * @brief Construit un objet de type ND-occupancy MDP. 
         */
        NDOccupancyMDP(const std::shared_ptr<NDPOMDPInterface> &ndpomdp, number memory = -1, bool compression = true, bool store_states = true, bool store_actions = true, int batch_size = 0);

        /**
         * @brief Définition de la dynamique.
         */
        Pair<std::shared_ptr<State>, std::shared_ptr<State>> computeExactNextState(const std::shared_ptr<State> &occupancy_state,
                                                                                   const std::shared_ptr<Action> &decision_rule,
                                                                                   const std::shared_ptr<Observation> &observation,
                                                                                   number t = 0);

        /**
         * @brief Définition de la récompense.
         */
        double getReward(const std::shared_ptr<State> &occupancy_state, 
                         const std::shared_ptr<Action> &decision_rule, 
                         number t = 0);

    };
} // namespace sdm

← Installation MDP →