New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
strips - npm Package Compare versions
Comparing version 0.0.3 to 0.0.4
| { | ||
| "name": "strips", | ||
| "version": "0.0.3", | ||
| "version": "0.0.4", | ||
| "description": "Basic AI planning with STRIPS and PDDL.", | ||
@@ -46,4 +46,4 @@ "author": { | ||
| ], | ||
| "_id": "strips@0.0.3", | ||
| "_id": "strips@0.0.4", | ||
| "_from": "strips" | ||
| } |
@@ -58,6 +58,12 @@ AI Planning with STRIPS | ||
| #### solve(domain, problem, isDepthFirstSearch = true, maxSolutions = 1) | ||
| #### solve(domain, problem, isDepthFirstSearch = true, maxSolutions = 1, cost = null) | ||
| 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. | ||
| Searches for a solution to the given problem by using depth-first-search, breadth-first-search, or A* search. | ||
| The default setting uses depth-first-search and returns the first solution found. To return more solutions, set maxSolutions to a higher value. | ||
| To use A* search, provide a function for the "cost" parameter, using the format cost(state), to serve as a heuristic for A*. The function should return an integer, representing the cost of the given state. See [starcraft.js](https://github.com/primaryobjects/strips/blob/master/starcraft.js) for an example. | ||
| The cost function may also be passed as the 3rd parameter (ie., solve(domain, problem, cost)). Note, you can also write your own solution algorithm by using the methods below. | ||
| #### getChildStates(domain, state) | ||
@@ -164,12 +170,33 @@ | ||
| Of course, the real power is in designing your own search algorithm using the strips methods. See the [default](https://github.com/primaryobjects/strips/blob/master/strips/strips.js#L440) search routine for an idea of how to use the methods to search. | ||
| Of course, the real power is in designing your own search algorithm using the strips methods. See the [default](https://github.com/primaryobjects/strips/blob/master/strips/strips.js#L566) search routine for an idea of how to use the methods to search. | ||
| ### A* Search | ||
| You can implement your own A* search to find a solution. A* works by using a heuristic to guide it down the path of possible moves in the domain. In this manner, it is much faster than simple breadth-first or depth-first search. It will also find an optimal solution that contains the least number of steps. | ||
| A* search works by using a heuristic to guide it down the path of possible moves in the domain. In this manner, it is much faster than simple breadth-first or depth-first search. It will also find an optimal solution that contains the least number of steps. | ||
| Since the strips library exposes its internal methods, you can implement your own search algorithm. Here is an [example](https://github.com/primaryobjects/strips/blob/master/starcraft.js) of an A* search method for the [starcraft](https://github.com/primaryobjects/strips/blob/master/examples/starcraft/domain.txt) domain, to train a [marine](https://github.com/primaryobjects/strips/blob/master/examples/starcraft/marine.txt). | ||
| Strips comes with a built-in A* search algorithm that accepts your own cost function to use as a heuristic. See the section "methods" above. You simply write your own cost function that takes "state" as input and returns an integer as the resulting cost. Here is an [example](https://github.com/primaryobjects/strips/blob/master/starcraft.js) cost function for the starcraft [domain](https://github.com/primaryobjects/strips/blob/master/examples/starcraft/domain.txt) to train a [marine](https://github.com/primaryobjects/strips/blob/master/examples/starcraft/marine.txt): | ||
| The core idea to a custom search method is to use the strips methods isGoal() and getChildStates() to iterate through all states and actions. Once you have a list of child states, apply your heuristic to calculate a cost for each state. Then sort the states by cost so that A* can choose the next cheapest state to move to. You can see the details in the example. | ||
| ```javascript | ||
| function cost(state) { | ||
| // This is our A* heuristic method to calculate the cost of a state. | ||
| // For Starcraft, the heuristic will be how many required buildings have been built. Subtract x from cost for each correct building, with 0 meaning all required buildings have been made and we're done. | ||
| var cost = 10; | ||
| for (var i in state.actions) { | ||
| var action = state.actions[i].action; | ||
| if (action == 'depot') { | ||
| cost -= 5; | ||
| } | ||
| else if (action == 'barracks') { | ||
| cost -= 5; | ||
| } | ||
| } | ||
| return cost; | ||
| } | ||
| ``` | ||
| You can also implement your own A* search to find a solution. Since the strips library exposes its internal methods, you can implement your own search algorithm. The core idea to a custom search method is to use the strips methods isGoal() and getChildStates() to iterate through all states and actions. Once you have a list of child states, apply your heuristic to calculate a cost for each state. Then sort the states by cost so that A* can choose the next cheapest state to move to. You can see the details in the solve() methods in strips. | ||
| Have fun! | ||
@@ -176,0 +203,0 @@ |
@@ -554,5 +554,10 @@ var fs = require('fs'); | ||
| solve: function(domain, problem, isDfs, maxSolutions) { | ||
| // Find solution. | ||
| if (isDfs == null) { | ||
| solve: function(domain, problem, isDfs, maxSolutions, cost) { | ||
| // Find solution using A*, depth-first, or breadth-first search. | ||
| if (typeof(isDfs) == 'function' && !cost) { | ||
| // Allow passing cost as 3rd parameter. | ||
| cost = isDfs; | ||
| } | ||
| else if (isDfs == null) { | ||
| // If no other option specified, use depth-first-search by default. | ||
| isDfs = true; | ||
@@ -563,4 +568,15 @@ } | ||
| return isDfs ? StripsManager.solveDfs(domain, problem.states[0], problem.states[1], maxSolutions) : | ||
| StripsManager.solveBfs(domain, problem.states[0], problem.states[1], maxSolutions); | ||
| if (cost && typeof(cost) != 'function') { | ||
| console.log('ERROR: parameter "cost" must be a function to serve as the A* algorithm heuristic. Method: solve(domain, problem, isDepthFirstSearch, cost, maxSolutions). Usage: solve(domain, problem), solve(domain, problem, false), solve(domain, problem, cost).'); | ||
| return; | ||
| } | ||
| if (StripsManager.verbose) { | ||
| console.log('Using ' + (cost ? 'A*' : (isDfs ? 'depth' : 'breadth') + '-first-search') + '.'); | ||
| console.log(''); | ||
| } | ||
| return cost ? StripsManager.solveAs(domain, problem.states[0], problem.states[1], cost) : | ||
| (isDfs ? StripsManager.solveDfs(domain, problem.states[0], problem.states[1], maxSolutions) : | ||
| StripsManager.solveBfs(domain, problem.states[0], problem.states[1], maxSolutions)); | ||
| }, | ||
@@ -634,3 +650,3 @@ | ||
| solveBfs: function(domain, state, goalState, maxSolutions) { | ||
| // Find first solution using breadth-first-search. | ||
| // Find all solutions using breadth-first-search. | ||
| var fringe = [ { state: state, depth: 0 } ]; // Start with the initial state on the fringe. | ||
@@ -691,2 +707,62 @@ var visited = {}; | ||
| return solutions; | ||
| }, | ||
| solveAs:function(domain, state, goalState, cost) { | ||
| // Find first solution using A* search, where cost is the heuristic function (h = cost(state)). Starting with the initial state, we find all children by applying applicable actions on the current state, calculate the child state costs, and select the next cheapest state to visit. | ||
| var depth = 0; | ||
| var fringe = [ { state: state, h: cost(state), g: depth } ]; // Start with the initial state on the fringe. | ||
| var visited = {}; | ||
| var solutions = []; | ||
| while (fringe.length > 0) { | ||
| // Investigate the next state with the lowest cost. | ||
| 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.g; | ||
| 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 }); | ||
| 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.g = current.g + 1; | ||
| child.h = cost(child.state); | ||
| if (!visited[StripsManager.stateToString(child.state)]) { | ||
| fringe.push(child); | ||
| } | ||
| } | ||
| fringe.sort(function(a, b) { return (a.h + a.g) - (b.h + b.g) }); | ||
| } | ||
| if (StripsManager.verbose) { | ||
| console.log('Depth: ' + current.g + ', Current cost: ' + (current.h + current.g) + ', ' + fringe.length + ' child states.'); | ||
| } | ||
| } | ||
| return solutions; | ||
| } | ||
@@ -693,0 +769,0 @@ }; |
No alert changes
Improved metrics
- Total package byte prevSize
- increased by5.91%
87912
- Lines of code
- increased by4.2%
1515
- Number of lines in readme file
- increased by14.84%
209
No dependency changes