AI Planning with STRIPS
This project is a demo of using the artificial intelligence automated planning library strips, in node.js.
Try it online at https://stripsfiddle.herokuapp.com
npm install strips
If you're new to STRIPS automated planning, here is a great tutorial to get you started.
The following examples show how to solve planning problems by identifying the optimal set of actions to achieve a goal. For example, stacking blocks, Towers of Hanoi, and even Starcraft can be solved by the AI (see below, it's pretty neat!).
Several examples from the Blocks World domain are included in this project, in which the AI is able to successfully plan the series of steps to move and stack blocks on a series of tables.
The domain and problem PDDL files are parsed via PEG.js, producing a JSON object for a given domain. The JSON is then processed to identify applicable actions within a given state of the problem. The actions are then applied to the current state, producing a new set of states. This process is repeated, where applicable actions are identified for the new states, applied, and further new states produced. The resulting tree of possible states and actions may then be traversed using the A* algorithm to locate an optimal set of steps to achieve the goal state, as specified in the problem.
Example Flow of Program
- Start with initial state.
- Identify valid actions for the current state.
- Apply actions on current state to produce child states.
- Repeat until goal state is found.
Example Blocks World Problems
Domain | Problem The fun one! Unstack blocks ba from table 1 to a stack ab on table 3. Only one block or stack is permitted on a table. The AI needs to plan for moving a block temporarily to table 2, while it sets up the correct order for stacking on table 3. Available actions include "move", "stack", and "unstack".
Example Output from Blocks World Problem #3
*** Solution found in 6 steps! 1. unstack a b t1 t2 2. move b t1 t3 3. move a t2 t1 4. move b t3 t2 5. move a t1 t3 6. stack a t3 b t2 *** Solution found in 5 steps! 1. unstack a b t1 t2 2. move b t1 t3 3. move a t2 t1 4. move b t3 t2 5. stack a t1 b t2 *** Solution found in 5 steps! 1. unstack a b t1 t2 2. move a t2 t3 3. move b t1 t2 4. move a t3 t1 5. stack a t1 b t2 *** Solution found in 4 steps! 1. unstack a b t1 t2 2. move a t2 t3 3. move b t1 t2 4. stack a t3 b t2 *** Solution found in 4 steps! 1. unstack a b t1 t3 2. move b t1 t2 3. move a t3 t1 4. stack a t1 b t2 *** Solution found in 3 steps! 1. unstack a b t1 t3 2. move b t1 t2 3. stack a t3 b t2
Sussman Anomaly Solution
*** Solution found in 3 steps! 1. unstack2 c a x 2. stack2 b c x 3. stack3 a b c x
*** Solution found in 8 steps! 1. move scv sector-a mineral-field-b 2. collect-minerals scv mineral-field-b 3. move scv mineral-field-b sector-b 4. build-supply-depot scv sector-b 5. move scv sector-b mineral-field-a 6. collect-minerals scv mineral-field-a 7. move scv mineral-field-a sector-a 8. build-barracks scv sector-a sector-b
One step further, here is the AI's solution for traning a marine.
- Solution found in 11 steps! 1. move scv sector-a mineral-field-a 2. collect-minerals scv mineral-field-a 3. move scv mineral-field-a sector-b 4. build-supply-depot scv sector-b 5. move scv sector-b mineral-field-b 6. collect-minerals scv mineral-field-b 7. move scv mineral-field-b sector-a 8. build-barracks scv sector-a sector-b 9. move scv sector-a mineral-field-c 10. collect-minerals scv mineral-field-c 11. train-marine scv sector-a
Kory Becker http://www.primaryobjects.com/kory-becker