Régressif Orienté Objectif Planification

Question

J'essaie actuellement de faire une recherche régressive à partir d'un état de but pour trouver une liste d'actions qui permettront d'atteindre l'état d'objectif de mon planificateur GOAP. Jusqu'à présent, le pseudo-code pour ce que j'ai vers le bas va comme ceci:

closedList = list; 
s = stack; 
s.push(goal); 
while(s.size() > 0) 
{ 
    state = s.pop; 
    if(!state exists in closedList) 
    { 
     closedList.add(state); 
     for(action = firstAction; action != lastAction; action = nextAction) 
     { 
      if(action.getEffect() == state) 
      { 
       if(!action.ConditionsFulfilled()) 
       { 
        conditionList = action.getConditions; 
        for(i = 0; i < conditionList.size(); i++) 
        { 
         s.push(conditionList[i]); 
        } 
       } 
      } 
     } 
    } 
} 

J'entends que GOAP est exactement comme un algorithme A * seulement que le noeud est l'état et les bords sont les actions. Mais comme dans un A *, il n'y a pas de conditions à remplir par un nœud, cela m'a rendu confus sur la façon d'adapter un algorithme A * pour travailler avec des conditions préalables. Ce que j'ai du mal à comprendre, c'est comment stocker les actions et comparer le coût des actions afin de trouver le chemin le plus efficace. Si nous supposons que l'action de classe a une fonction getCost() qui retourne le coût de l'action, comment ferais-je cela en considérant les conditions préalables?

Answer 1

Les nœuds sont en effet des états du monde. Et les bords sont des actions. Mais notez que ce sont des bords dirigés! Lorsque les conditions préalables sont entrées: Elles déterminent les bords (actions) qui sortent du noeud. Seules les actions dont les conditions préalables sont remplies sont des arêtes valides qui sortent de ce noeud d'état. Donc, pour trouver les voisins d'un nœud, vous devez vérifier chaque action si toutes les conditions préalables sont remplies. Si c'est le cas, appliquez les postconditions pour voir le nœud auquel l'action aboutira. L'action est alors un tronçon valide entre ces états (nœuds.)

Veuillez consulter la section (Planification d'actions orientée objet à usage général) pour une implémentation de GOAP avec A *. C'est un code simple en C qui explique toutes les étapes. Je suis l'auteur de GPGOAP.

Réflexions sur la régression

Maintenant, pour la partie régressive: je n'ai jamais mis en œuvre une recherche en arrière de but à l'état du monde actuel. Je peux donc être d'une aide limitée sur ce front.

Deux nœuds voisins seront toujours connectés sur la base d'une seule action. Vous activez/désactivez les arêtes non basées sur la condition préalable de l'action, mais sur la post-condition de l'action. Si la condition de publication ne correspond pas au noeud actuel, l'action ne sera pas valide. Si c'est le cas, je m'attends à ce que vous ajoutiez le voisin en forçant la pré-condition de l'action.

Quelle est votre raison de préférer la recherche en amont à la recherche en avant?