strips - npm Package Compare versions

Comparing version 0.0.6 to 0.0.7

package.json

 {
   "name": "strips",
-  "version": "0.0.6",
+  "version": "0.0.7",
   "description": "Basic AI planning with STRIPS and PDDL.",
@@ -38,2 +38,5 @@ "author": {
     "ai planning",
+    "planning graph",
+    "partial planner",
+    "partial order plan",
     "stanford research institute problem solver",
@@ -47,4 +50,4 @@ "problem solver",
   ],
-  "_id": "strips@0.0.6",
+  "_id": "strips@0.0.7",
   "_from": "strips"
 }

Readme.md

@@ -68,2 +68,16 @@ AI Planning with STRIPS
 
+#### graph(domain, problem, minLayers = 0, maxLayers = 0, isSkipNegativeLiterals = false)
+
+Returns a planning [graph](https://github.com/primaryobjects/strips/blob/master/examples/dinner/images/birthday-dinner.jpg) for a [domain](https://github.com/primaryobjects/strips/blob/master/examples/dinner/domain.pddl) and [problem](https://github.com/primaryobjects/strips/blob/master/examples/dinner/problem.pddl).
+
+The planning graph is returned as an array of actions in JSON. In each action, 'precondition' represents parent literals. 'effect' represents child literals. Any action not named 'noop' (no-operation) represents an applicable action, based on the preceding literals. 'noop' is simply a placeholder action to carry each literal forward, from one layer to the next.
+
+Each layer consists of 3-tiers: P0 (literals), A1 (actions), P1 (literals). The format is: P0 = precondition, A1 = actions, P1 = effect.
+
+The planning graph continues adding layers until no new literals and no new actions are discovered. The resulting graph can be used with [GraphPlan](http://en.wikipedia.org/wiki/Graphplan) or other search algorithms. For details on using GraphPlan, see [here](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-825-techniques-in-artificial-intelligence-sma-5504-fall-2002/lecture-notes/Lecture12FinalPart1.pdf) and [here](http://www.grastien.net/ban/teaching/06-planning5.pdf).
+
+If isSkipNegativeLiterals = true, negative literals (mutex) created from an action will be ignored. If you want to include complementary actions in the graph (such as 'Action A on A'), set strips.fast = false.
+
+See [example](https://github.com/primaryobjects/strips/blob/master/graph.js#L19-L30).
+
 #### getChildStates(domain, state)
@@ -102,3 +116,3 @@
 
-Defaults to true, which uses permutationCombination to calculate possible parameter values for actions. Set this property to false to use baseN instead. Using baseN is slower, but will allow strips to utilize all possible solutions. Changing this setting is only necessary if you are unable to find a solution plan using the default setting.
+Defaults to true, which uses permutationCombination to calculate possible parameter values for actions. Set this property to false to use baseN instead. Using baseN is slower, but will allow strips to utilize all possible solutions. This allows rendering of 'complementary actions', such as 'Action A on A', where normally you would want 'Action A on B'. Changing this setting is only necessary if you are unable to find a solution plan using the default setting.
 
@@ -105,0 +119,0 @@ #### strips.verbose

strips.js

@@ -16,3 +16,3 @@ var fs = require('fs');
 StripsManager = {
-    // Set to false to use baseN() instead of permutationCombination() for parameter values. It will be slower, but will utilize all possible solutions.
+    // Set to false to use baseN() instead of permutationCombination() for parameter values. It will be slower, but will utilize all possible solutions. This allows rendering of 'complementary actions', such as 'Action A on A', where normally you want 'Action A on B'.
     fast: true,
@@ -172,3 +172,3 @@ // Set to true to display status information on the console while searching for a solution.
             // Get a combination of all possibilities of the discovered parameters.
-            var cmb = combinatorics.permutation(cases, parameters.length);
+            var cmb = StripsManager.fast ? combinatorics.permutation(cases, parameters.length) : combinatorics.baseN(cases, parameters.length);
 
@@ -292,3 +292,3 @@ // Filter the combinations to valid parameter types and unique combos.
                 if (match) {
-                    // This action exists in the state.
+                    // This action exists in the state.                    
                     if (operation == 'and') {
@@ -346,2 +346,77 @@ matchCount++;
     
+    applicableActionsPlus: function(domain, state) {
+        // Returns an array of applicable concrete actions for the current state, including support for negative literals. This method runs StripsManager.applicableActions() two times - one with all positive literals (negative literals removed, which effectively renders all positive literal cases), and one with all positive literals with none that had matching negative literals (which effectively renders all negative literal cases). The result includes a list of unique actions.
+        var result = [];
+        var actionHash = {};
+
+        // Remove negative literals.
+        var stateNoNegatives = JSON.parse(JSON.stringify(state));
+        stateNoNegatives.actions = [];
+        for (var i in state.actions) {
+            var action = state.actions[i];
+
+            if (action.operation != 'not') {
+                // Not a negative literal, so keep it.
+                stateNoNegatives.actions.push(action);
+            }
+        }
+
+        // Get applicable actions.
+        var actions = StripsManager.applicableActions(domain, stateNoNegatives);
+
+        // Mark each action as discovered.
+        for (var i in actions) {
+            var action = actions[i];
+
+            result.push(action);
+            actionHash[JSON.stringify(action)] = 1;
+        }
+
+        // Remove matching positive and negative literals, effectively rendering the negative literal.
+        var literalsToRemove = {};
+        var stateNoPositiveNegatives = JSON.parse(JSON.stringify(state));
+        stateNoPositiveNegatives.actions = [];
+
+        // First, collect negative literals.
+        for (var i in state.actions) {
+            var action = state.actions[i];
+            action.operation = action.operation || 'and';
+
+            if (action.operation == 'not') {
+                // Make a copy of the positive version of this literal.
+                var copyAction = JSON.parse(JSON.stringify(action));
+                copyAction.operation = 'and';
+
+                // Mark the positive version of this literal to be removed (if we come across it).
+                literalsToRemove[JSON.stringify(copyAction)] = 1;
+            }
+        }
+
+        // Now that we've marked negative literals, go through all literals and only keep those which are positive and not included in the literalsToRemove.
+        for (var i in state.actions) {
+            var action = state.actions[i];
+            action.operation = action.operation || 'and';
+
+            // If this is a positive literal and not in our literalsToRemove list, then include it.
+            if (action.operation != 'not' && !literalsToRemove[JSON.stringify(action)]) {
+                // Safe to keep this literal.
+                stateNoPositiveNegatives.actions.push(action);
+            }
+        }
+
+        // Get applicable actions when allowing for negative literals.
+        actions = StripsManager.applicableActions(domain, stateNoPositiveNegatives);
+
+        // Concat new actions.
+        for (var i in actions) {
+            var action = actions[i];
+
+            if (!actionHash[JSON.stringify(action)]) {
+              result.push(action);
+            }
+        }
+
+        return result;
+    },
+
     applicableActions: function(domain, state) {
@@ -768,2 +843,115 @@ // Returns an array of applicable concrete actions for the current state, using the possible parameter values in domain.values array (Example: values = ['a', 'b', 't1', 't2', 't3']).
         return solutions;
+    },
+
+    nextGraphLayer: function(domain, parentLayer, isSkipNegativeLiterals) {
+        // Builds the next planning graph layer, based upon the previous layer. In each action, 'precondition' represents parent literals. 'effect' represents child literals.
+        // Returns a 3-tier layer, consisting of P0 (literals), A0 (actions), P1 (literals). The format is: P0 = precondition, A0 = all actions not named 'noop', P1 = effect.
+        // If isSkipNegativeLiterals = true, negative literals (mutex) created from an action will be ignored.
+        var layer = [];
+        var literalHash = {};
+        var literalCount = 0;
+        var actionCount = 0;
+
+        // Pack all literals from actions in this layer into a single array.
+        var children = { effect: [] };
+        for (var i in parentLayer) {
+            for (var j in parentLayer[i].effect) {
+                var literal = parentLayer[i].effect[j];
+                literal.operation = literal.operation || 'and';
+
+                if (!isSkipNegativeLiterals || (isSkipNegativeLiterals && literal.operation != 'not')) {
+                    if (!literalHash[JSON.stringify(literal)]) {
+                        children.effect.push(literal);
+
+                        // P2 - Carry forward literals from parent, using noop actions.
+                        var noop = { action: 'noop' };
+                        noop.precondition = noop.precondition || [];
+                        noop.precondition.push(literal);
+                        noop.effect = noop.precondition;
+                        layer.push(noop);
+
+                        literalHash[JSON.stringify(literal)] = 1;
+                
+                        // Keep a count of all literals in this layer so we know if we found any new ones after graphing.
+                        literalCount++;
+                    }
+                }
+            }
+        }
+
+        // A1 - Get all applicable actions for the state.
+        var actions = StripsManager.applicableActionsPlus(domain, { actions: children.effect });
+        actionCount = actions.length;
+        for (var i in actions) {
+            // Add action to the layer, preconditions are the parents, effects are the children.
+            layer.push(actions[i]);
+        }
+
+        if (StripsManager.verbose) {
+            console.log('P' + lastGraphIndex + ': ' + lastLiteralCount + ', A' + (lastGraphIndex+1) + ': ' + lastActionCount + ', P' + (lastGraphIndex+1) + ': ' + literalCount + ', A' + (lastGraphIndex+2) + ': ' + actionCount);
+        }
+
+        lastGraphIndex++;
+        lastLiteralCount = literalCount;
+
+        // If we discovered new literals or new actions, then return the layer and continue building the graph.
+        if (lastLiteralCount > literalCount || lastActionCount != actionCount) {
+            lastActionCount = actionCount;
+
+            return layer;
+        }
+        else {
+            // No change, no new literals.
+            layer.done = true;
+            return layer;
+        }
+    },
+
+    graph: function(domain, problem, minLayers, maxLayers, isSkipNegativeLiterals) {
+        // Builds a planning graph for a domain and problem. In each action, 'precondition' represents parent literals. 'effect' represents child literals. Any action not named 'noop' represents an applicable action.
+        // Each layer consists of 3-tiers: P0 (literals), A0 (actions), P1 (literals). The format is: P0 = precondition, A0 = actions, P1 = effect.
+        // Loops, building new graph layers, until no new literals and no new actions are discovered.
+        // If isSkipNegativeLiterals = true, negative literals (mutex) created from an action will be ignored.
+        var result = [];
+        var layer = [];
+        var actionHash = {};
+
+        // P0 - initial literals.
+        for (var i in problem.states[0].actions) {
+            // P1 - B. Carry forward literals from parent.
+            var noop = { action: 'noop' };
+            noop.precondition = noop.precondition || [];
+            noop.precondition.push(problem.states[0].actions[i]);
+            noop.effect = noop.precondition;
+            layer.push(noop);    
+        }
+
+        // A0 - Get all applicable actions for the initial state.
+        var actions = StripsManager.applicableActionsPlus(domain, problem.states[0]);
+        
+        // Initialize global graph helper counters.
+        lastLiteralCount = layer.length;
+        lastActionCount = actions.length;
+        lastGraphIndex = 0;
+
+        layer = layer.concat(actions);
+
+        // Add the literals, actions, next literals to the graph (P0, A0, P1).
+        result.push(layer);
+
+        // Next layer.
+        var index = 0;
+        var layer = StripsManager.nextGraphLayer(domain, result[index++], isSkipNegativeLiterals);
+        while ((!layer.done || (minLayers && index < minLayers)) && (!maxLayers || index < maxLayers)) {
+            if (StripsManager.verbose) {
+                console.log('Processing layer ' + index);
+            }
+
+            result.push(layer);
+
+            // Get next graph layer.
+            layer = StripsManager.nextGraphLayer(domain, result[index++], isSkipNegativeLiterals);
+        }
+
+        return result;
     }
@@ -770,0 +958,0 @@ };

No alert changes

Improved metrics

Total package byte prevSize

97404

increased by12.11%

Lines of code

1667

increased by10.03%

Number of lines in readme file

223

increased by6.7%

No dependency changes