Planning is essential for agents that act in an environment. To solve a goal intelligently, an agent needs to think about whatit will do now and in the future. This applet demonstrates planning using the blockworld problem domain and STRIPS representation. In the blockworld problem, a robot gripper must arrange a set of blocks into a particular configuration on the table. A block may be on the table, or placed on top of another block. The gripper can only hold one block at a time, and can only pick up blocks that have no other blocks on top of them. The problem is modeled by the following propositions:
This applet uses the STRIPS representation to demonstrate the STRIPS, regression, and partial order planners. In the STRIPS representation, actions are represented as a set of preconditions, an add list, and a delete list. For an action to be carried out, all of its precondions must be true in the world. When the action is performed, items in the add list are added to the world's current state while items in the delete list are removed from it. The following actions are used to control the gripper in the blockworld problem:
Note that the action pickup is used to pick up a block that is sitting on another block, while pickuptable is used for a block that is sitting on the table. Likewise, putdown is used to put a block down on top of another block, while putdowntable is used to put a block on the table. In this problem, the positions of the blocks on the table is not important; the goal is to stack blocks on top of each other in particular patterns.
This planning applet provides a "Create" mode that provides several ways to load, view, and build blockworld problems. In "Solve" mode, the applet provides tools for visualizing how a plan is constructed to move blocks from the initial state in order to achieve the specified goals.
Graph Options Menu
The Planning applet's Create Mode is used to view and/or create blockworld planning problems. The large white canvas area displays a table on which blocks can be placed and manipulated. There are two text displays below the table that show the text representation of the initial state and goals. The buttons above the text panels provides tools for defining the problem, which consists of an initial state and a goal state to achieve.
Planning problems can be acquired by loading a sample problem or defining a new problem in "Create" mode. To load a sample problem, click "Load Sample Problem" from the "File" menu. Then select a problem from the drop-down list and click "Load." The problem's initial state will then be displayed as blocks stacked on the table and the text representation of the problem's initial state and goals will be visible in the text displays below the block table. You can now modify the problem or switch to "Create" mode to begin searching for a plan.
To create a new planning problem, select "Create New Problem" from the "File" menu. When creating a problem, the first step is to define the initial state. This is the starting positions of all the blocks in the problem. Be sure that you are in "Create Initial State" mode, as indicated by the options on the left-side control panel. You can now create blocks by selecting "Create New Block" on the button panel and then clicking the position on the table where the new block is to appear. A block properties window will then open. You can click the "Ok" button to proceed or change the block's name and/or colour before clicking "Ok." Clicking again on the canvas will create another block. Use the modes on the button panel to delete blocks and change the block's properties (name and colour). Note that blocks can be rearranged by dragging them to new positions on the table or onto other blocks. As blocks are created or rearranged, the Prolog-style text representation of the initial state is displayed and updated in the Initial State box below the table.
Once the initial state has been created, the goals for the planner to achieve must be specified. Goals can be specified visually by rearranging the blocks of the initial state, or the goals can be specified by manually choosing goal atoms and terms.
Creating Goals Visually After creating the initial state, select "Create Goal State" button. When asked to select a goal entry method, select the first option, "Specify goal state by graphically rearranging the initial state." You can now move blocks around to create the goal state. Notice how the goals display in the lower right corner text display change as you move the blocks.
If desired, you can click the "Reorder Goals" button to change the order of the goals to be achieved. To adjust the order of a goal, select it with your mouse so that it is highlighted. Then click the "Move Goal Up" or "Move Goal Down" buttons to move the goal to the desired position. Goals closer to the top of the list will have priority.
Creating Goals by Specifying Goal Atoms and Terms When you specify goals visually, the goals can sometimes be overspecified. You may only be concerned about a few block positions rather than the position of every block in the world. If you need more control over the goals, they can be entered individually instead of visually. In this case, select "Specify Goals" on the control panel and when asked to select a goal entry method, select the second option, "Specify Goals by Entering Atoms." If you are currently in visual goal specification mode, you can change the mode by choosing the radio buton "Specify Goals by Entering Atoms" at the bottom of the Goal State panel. There will now be two new buttons available on the button panel, "Add New Goal" and "RemoveGoals" Clicking "Add New Goal" opens a window that helps you specify goals. First choose from the available predicates in the drop-down list. If the predicate requires one or more terms, the window will update to display drop-down boxes you can use to select each term. If the term you need is a simple constant, a block, then just select the block name. If you would like to use a variable as a term, select "variable" from the drop down box. You will then be prompted for the name of the variable. When you have selected all required terms, click "Add Goal" to continue. You can repeat this process as many times as necessary to specify your goals. If you would like to delete a goal, click the "Remove Goals" button to select the goals to remove.
Note that once a goal entry method has been chosen, the program will default to that method whenever "Create Goal State" is selected. If you want to change goal entry method later, you may do so via the radio buttons on the bottom of the Goal panel.
Combining Goal Entry Methods In some cases, it may be convenient to combine goal entry methods. For example, you may want to define an initial state, rearrange the initial state to define a goal state, and then remove some goals that are not important to the problem you wish to define. In this case, proceed with defining the initial state and goal state in Visual Goal Entry mode. Then use the options menu to switch to "Specify Goals by Entering Atoms" mode. You can now fine-tune the goals using the control panel buttons "Remove Goals" and "Add Goals"
When the initial state and goals of a planning problem have been created (or loaded), select the "Solve" tab at the top of the control panel. In this mode, a tree is created as a visual representation of how the STRIPS planner works. Rectangular nodes represent actions oval nodes represent subgoals of the parent action. Red action nodes indicate that the action has not been added to the plan, and red goal nodes are goals that have not been achieved. Green action nodes have been added to the plan and green goal nodes have been achieved.
Initially, the tree consists of a root node labelled "Solved" and the initial goals are visualized as subgoals of the root action node, "Solved." Click the "Step" button to watch the algorithm attempt to find a plan by choosing actions to achieve all of the goals.
While the algorithm is running, it is helpful to open the Current State window (Click "View Current State"). This window visually displays the current position of all the blocks and also shows the text representation of the current state. You can also click "View Plan" to view actions that have been added to the plan at the current stage of the algorithm.
If the algorithm is able to find a plan, you may wish to view an animation of that plan by clicking the "Run Plan" button. This will open a window showing the initial state of the planning problem. You can then press the "Run Plan" button to begin the animation.
Selecting "Algorithm Options" from the "Graph Options" menu will open a window you can use to view and modify settings for the STRIPS algorithm. Here you can select the method of handling situations where an action undoes previously achieved goals. The two options are "Reachieve Subgoals," and "Protect Subgoals." If you choose to reachieve, subgoals that have been undone will be added to the tree as new goals at the last possible opportunity, which is when an action is about to be performed because all other preconditions have been met. If you choose to protect subgoals, then actions that will undo a previously achieved subgoal will not be accepted. This may cause the search for a plan to fail.
This version supports visualization of the STRIPS planner. Future versions of this applet will also demonstrate regression and partial order planners.
The STRIPS planner achieves a list of goals by choosing one unachieved goal at a time. If this goal is true in the world, then the algorithm proceeds to the next goal. If the goal is not true, then an action is chosen that will make the goal true. The preconditions of the action then become subgoals that must be achieved before the action is added to the plan. The algorithm continues until all goals have been achieved. However, the planner may not always be successful. It may never terminate or, if protecting subgoals, it may halt because there are no actions that won't undo subgoals. In some cases, changing the order in which subgoals are tackled may allow a solution to be found when the algorithm would otherwise fail.
|Main Tools: Graph Searching | Consistency for CSP | SLS for CSP | Deduction | Belief and Decision Networks | Decision Trees | Neural Networks | STRIPS to CSP|