Regressive search is probably a bit smarter

[seivan]

I would suggest going backwards makes more sense when pathfinding to endState. https://github.com/sploreg/goap/blob/master/Assets/Standard%20Assets/Scripts/AI/GOAP/GoapPlanner.cs#L93

That way you give the AI a higher chance of finding a solution that works instead of a predefined set of actions that give you the result. In other words, you should match endState with postEffects and the action's postEffects with next actions preConditions or existing startState.

endState -> postEffects -> preConditions/startState Though you want to make sure to always check against the startState for every action because you could end the planning earlier since it might just be sufficient enough from where you are.

[flamelstone]

Unclear if the project is still maintained but I've implemented backward pathfinding as you suggested (in a somewhat stable form?) and it is much much faster and efficient as buildGraph() does not draw full trees for every single combination of options (which the GC hates) but only for those that have a chance of succeeding.

Edit: Anecdotal comparison, with 10 actions and 10 plans to find, the original model took roughly 2.5min to complete; with backward pathfinding it takes less than 0.20 seconds.

[miroslavzeman]

@flamelstone Hey! I have been looking for regressive search implementation and couldn't find any... Is there any chance you could share your implementation with us?

[deanvaessen]

Seconded, would be super useful if you could share it @flamelstone

[flamelstone]

@miro4994 @deanvaessen

Sorry for the delay, life got really busy and I couldn't get around to answering you guys. Hereafter is the code I used to implement a regressive search. A few things have to be mentioned however: I implemented this in a C# context, so a lot of unity specific language has been switched to regular bools or whatnot; also this was one of the first time I was playing around with C# and coding in general so it's probably very rough and I cannot guarantee anything in terms of performance or even safety.

In essence, the trick to make it regressive is to replace every precondition by the effect.

I hope this helps and I will try my best to answer any question you may have though again I am myself very much of a neophyte and it's been a while since I worked on this specifically.

using System.Linq;
using System;
using System.Collections.Generic;
using Core;

namespace GOAPWorld {

    /**
     * Plans what actions can be completed in order to fulfill a goal state.
     */
    public class GoapPlanner {

        /**
         * Plan what sequence of actions can fulfill the goal.
         * Returns null if a plan could not be found, or a list of the actions
         * that must be performed, in order, to fulfill the goal.
         */
        public Queue<GoapAction> plan (GoapAgent agent,
            HashSet<GoapAction> availableActions,
            HashSet<KeyValuePair<string, bool>> worldState,
            HashSet<KeyValuePair<string, bool>> goal) {
            // reset the actions so we can start fresh with them
            foreach (GoapAction a in availableActions) {
                a.doReset ();
            }

            // check what actions can run using their checkProceduralPrecondition
            HashSet<GoapAction> usableActions = new HashSet<GoapAction> ();
            foreach (GoapAction a in availableActions) {
                if (a.checkProceduralPrecondition (agent))
                    usableActions.Add (a);
            }

            // we now have all actions that can run, stored in usableActions

            // build up the tree and record the leaf nodes that provide a solution to the goal.
            List<Node> leaves = new List<Node> ();

            // build graph
            Node start = new Node (null, 0, goal, null);
            HashSet<KeyValuePair<string, bool>> end = worldState;
            bool success = buildGraph (end, start, leaves, usableActions, goal);

            if (!success) {
                // oh no, we didn't get a plan
                // HERE! 
                Console.WriteLine ("NO PLAN for ");
                return null;
            }

            // get the cheapest leaf
            Node cheapest = null;
            foreach (Node leaf in leaves) {
                if (cheapest == null)
                    cheapest = leaf;
                else {
                    if (leaf.runningCost < cheapest.runningCost)
                        cheapest = leaf;
                }
            }

            // get its node and work back through the parents
            List<GoapAction> result = new List<GoapAction> ();
            Node n = cheapest;
            while (n != null) {
                if (n.action != null) {
                    result.Add (n.action); // add the action at the end of the list
                }
                n = n.parent;
            }
            // we now have this action list in correct order

            Queue<GoapAction> queue = new Queue<GoapAction> ();
            foreach (GoapAction a in result) {
                queue.Enqueue (a);
            }

            // hooray we have a plan!
            return queue;
        }

        /**
         * Returns true if at least one solution was found.
         * The possible paths are stored in the leaves list. Each leaf has a
         * 'runningCost' value where the lowest cost will be the best action
         * sequence.
         */
        private bool buildGraph (HashSet<KeyValuePair<string, bool>> end, Node parent, List<Node> leaves, HashSet<GoapAction> usableActions, HashSet<KeyValuePair<string, bool>> goal) {
            bool foundOne = false;

            // go through each action available at this node and see if we can use it here
            foreach (GoapAction action in usableActions) {

                // if the parent state has the conditions for this action's preconditions, we can use it here
                if (inState (action.Effects, parent.state)) {

                    // apply the action's effects to the parent state
                    HashSet<KeyValuePair<string, bool>> currentState = populateState (parent.state, action.Effects, action.Preconditions);
                    // Console.WriteLine (GoapAgent.prettyPrint (currentState));
                    // Console.WriteLine("");
                    Node node = new Node (parent, parent.runningCost + action.cost, currentState, action);

                    if (inState (currentState, end)) {
                        // we found a solution!
                        leaves.Add (node);
                        foundOne = true;
                    } else {
                        // not at a solution yet, so test all the remaining actions and branch out the tree
                        HashSet<GoapAction> subset = actionSubset (usableActions, action);
                        bool found = buildGraph (end, node, leaves, subset, goal);
                        if (found)
                            foundOne = true;
                    }
                }
            }

            return foundOne;
        }

        /**
         * Create a subset of the actions excluding the removeMe one. Creates a new set.
         */
        private HashSet<GoapAction> actionSubset (HashSet<GoapAction> actions, GoapAction removeMe) {
            HashSet<GoapAction> subset = new HashSet<GoapAction> ();
            foreach (GoapAction a in actions) {
                if (!a.Equals (removeMe))
                    subset.Add (a);
            }
            return subset;
        }

        /**
         * Check that all items in 'test' are in 'state'. If just one does not match or is not there
         * then this returns false.
         */
        private bool inState (HashSet<KeyValuePair<string, bool>> test, HashSet<KeyValuePair<string, bool>> state) {
            bool allMatch = true;
            foreach (KeyValuePair<string, bool> t in test) {
                bool match = false;
                foreach (KeyValuePair<string, bool> s in state) {
                    if (s.Equals (t)) {
                        match = true;
                        break;
                    }
                }
                if (!match)
                    allMatch = false;
            }
            return allMatch;
        }

        /**
         * Apply the stateAdd to the currentState
         */
        private HashSet<KeyValuePair<string, bool>> populateState (HashSet<KeyValuePair<string, bool>> currentState, HashSet<KeyValuePair<string, bool>> stateRemove, HashSet<KeyValuePair<string, bool>> stateAdd) {
            HashSet<KeyValuePair<string, bool>> state = new HashSet<KeyValuePair<string, bool>> ();
            // copy the KVPs over as new objects
            foreach (KeyValuePair<string, bool> s in currentState) {
                state.Add (new KeyValuePair<string, bool> (s.Key, s.Value));
            }

            foreach (KeyValuePair<string, bool> change in stateRemove) {
                // if the key exists in the current state, remove it
                bool exists = false;

                foreach (KeyValuePair<string, bool> s in state) {
                    if (s.Equals (change)) {
                        exists = true;
                        break;
                    }
                }

                if (exists) {
                    state.RemoveWhere ((KeyValuePair<string, bool> kvp) => { return kvp.Key.Equals (change.Key); });
                }
            }

            foreach (KeyValuePair<string, bool> change in stateAdd) {
                // if the key exists in the current state, update the Value
                bool exists = false;

                foreach (KeyValuePair<string, bool> s in state) {
                    if (s.Equals (change)) {
                        exists = true;
                        break;
                    }
                }

                if (exists) {
                    state.RemoveWhere ((KeyValuePair<string, bool> kvp) => { return kvp.Key.Equals (change.Key); });
                    KeyValuePair<string, bool> updated = new KeyValuePair<string, bool> (change.Key, change.Value);
                    state.Add (updated);
                }
                // if it does not exist in the current state, add it
                else {
                    state.Add (new KeyValuePair<string, bool> (change.Key, change.Value));
                }
            }
            return state;
        }

        /**
         * Used for building up the graph and holding the running costs of actions.
         */
        private class Node {
            public Node parent;
            public float runningCost;
            public HashSet<KeyValuePair<string, bool>> state;
            public GoapAction action;

            public Node (Node parent, float runningCost, HashSet<KeyValuePair<string, bool>> state, GoapAction action) {
                this.parent = parent;
                this.runningCost = runningCost;
                this.state = state;
                this.action = action;
            }
        }

    }

}`

[vi-jasonm]

The resulting queue with this solution comes out backwards so when the GoapAgent "peeks" at it the result is the last node in the queue rather than the first one to be executed. Reversing the queue negates a lot of the speed improvements that the regressive search may have obtained.

In tests, with this in place, the regressive search with two actions actually came out slower for me (146ms vs 92ms).

[AronDavis]

@vi-jasonm so use a Stack instead of a Queue.