strips - npm Package Compare versions

Comparing version 0.0.1 to 0.0.2

package.json

 {
   "name": "strips",
-  "version": "0.0.1",
+  "version": "0.0.2",
   "description": "Basic AI planning with STRIPS and PDDL.",
@@ -46,4 +46,4 @@ "author": {
   ],
-  "_id": "strips@0.0.1",
+  "_id": "strips@0.0.2",
   "_from": "strips"
 }

Readme.md

@@ -47,6 +47,2 @@ AI Planning with STRIPS
 3. stack a b y
-- Solution found in 3 steps!
-1. move b x y
-2. move a x y
-3. stack a b y
 ```
@@ -60,2 +56,6 @@
 
+###### solve(domain, problem, isDepthFirstSearch = true, maxSolutions = 1)
+
+Searches for a solution to the given problem by using depth-first-search or breadth-first-search. The default setting uses depth-first-search and returns the first solution found. To return more solutions, set maxSolutions to a higher value. Note, you can write your own solution algorithm by using the methods below.
+
 ###### getChildStates(domain, state)
@@ -62,0 +62,0 @@

strips.js

@@ -435,8 +435,16 @@ var fs = require('fs');
 
-    solve: function(domain, problem) {
+    solve: function(domain, problem, isDfs, maxSolutions) {
         // Find solution.
-        return StripsManager.run(domain, { state: problem.states[0] }, problem.states[1]);
+        if (isDfs == null) {
+            isDfs = true;
+        }
+        
+        maxSolutions = maxSolutions || 1;
+
+        return isDfs ? StripsManager.solveDfs(domain, problem.states[0], problem.states[1], maxSolutions) :
+                       StripsManager.solveBfs(domain, problem.states[0], problem.states[1], maxSolutions);
     },
 
-    run: function(domain, state, goalState, visited, depth) {
+    solveDfs: function(domain, state, goalState, maxSolutions, visited, depth) {
+        // Find all solutions using depth-first-search.
         var solutions = [];
@@ -446,2 +454,3 @@
         depth = depth || 0;
+        state = state.state ? state : { state: state }; // format state to mirror child, which includes parent and action in recursion.
 
@@ -483,3 +492,3 @@ // If this is the initial state, add it to the visited list.
                     visited[key] = 1;
-                    var subSolutions = StripsManager.run(domain, child, goalState, visited, depth + 1);
+                    var subSolutions = StripsManager.solveDfs(domain, child, goalState, maxSolutions, visited, depth + 1);
                     if (subSolutions.length > 0) {
@@ -489,3 +498,11 @@ // This branch has a solution(s).
                             solutions.push(subSolutions[j]);
+
+                            if (solutions.length >= maxSolutions) {
+                                break;
+                            }
                         }
+
+                        if (solutions.length >= maxSolutions) {
+                            break;
+                        }
                     }
@@ -497,2 +514,61 @@ }
         return solutions;
+    },
+
+    solveBfs: function(domain, state, goalState, maxSolutions) {
+        // Find first solution using breadth-first-search.
+        var fringe = [ { state: state, depth: 0 } ]; // Start with the initial state on the fringe.
+        var visited = {};
+        var depth = 0;
+        var solutions = [];
+
+        while (fringe.length > 0) {
+            // Investigate the next state with the lowest depth.
+            var current = fringe[0];
+
+            // Remove this state from the fringe.
+            fringe.shift();
+
+            // Mark this state as visited.
+            visited[StripsManager.stateToString(current.state)] = 1;
+
+            // Check for goal.
+            if (StripsManager.isGoal(current.state, goalState)) {
+                // Compile solution path.
+                var path = [];
+                var steps = current.depth;
+
+                while (current != null && current.parent != null) {
+                    // Since we move from goal backwards, add this step to the front of the array (rather than the end, otherwise it would be in reverse order).
+                    path.unshift(StripsManager.actionToString(current.action));
+                    current = current.parent;
+                }
+
+                solutions.push({ steps: steps, path: path });
+
+                if (solutions.length >= maxSolutions) {
+                    return solutions;
+                }
+            }
+            else {
+                // Get child states by applying actions to current state.
+                var children = StripsManager.getChildStates(domain, current.state);
+
+                // Add the children to the fringe.
+                for (var i in children) {
+                    var child = children[i];
+                    child.parent = current;
+                    child.depth = current.depth + 1;
+
+                    if (!visited[StripsManager.stateToString(child.state)]) {
+                        fringe.push(child);
+                    }
+                }
+            }
+
+            if (StripsManager.verbose) {
+                console.log('Depth: ' + current.depth + ', ' + fringe.length + ' child states.');
+            }
+        }
+
+        return solutions;
     }
@@ -499,0 +575,0 @@ };

No alert changes

Improved metrics

Total package byte prevSize

73480

increased by4.67%

Lines of code

1357

increased by4.63%

No dependency changes