State Space Search Definition
2017 DC Pankratz
Project Developer: Bryan Kelly
Introduction
State – Space search techniques are used in situations where something needs to move to a destination but must avoid obstacles or barriers. Examples include manufacturing plants where products need to be moved from one line to another or to/from loading docks. Fixed barriers might include machines and walls, while variable barriers could include other movable blocks, parked fork trucks, etc. Other examples are cutting lawn on a golf course, boats in working harbors, highways with accidents, road construction and traffic jams.
Project Description
Develop an application that employs a variety of state-space searches an heuristics to determine optimal solutions for a robot to move objects to their goal locations.
Here is a good starting point. Consider the grid-space robot task of pushing a block to a given location or goal. The grid is bounded and has immovable barriers. Assume that the robot can sense its eight surrounding cells and can determine whether an occupied surrounding cell contains an immovable barrier (including a wall), a pushable block, or nothing. The robot can move up/down or left/right, but not diagonally. The robot is to move the block from its initial position to its goal position in as few moves as possible.
Here is a good starting point. Consider the grid-space robot task of pushing a block to a given location or goal. The grid is bounded and has immovable barriers. Assume that the robot can sense its eight surrounding cells and can determine whether an occupied surrounding cell contains an immovable barrier (including a wall), a pushable block, or nothing. The robot can move up/down or left/right, but not diagonally. The robot is to move the block from its initial position to its goal position in as few moves as possible.
General Requirements
- Solve the problem for a fixed initial configuration of dimensions, barriers, starting location of robot and block, and goal location of block as described above. Make sure to sue a variety of configurations.
- Employ both uninformed and informed search techniques.
- Analyze the effectiveness of using different heuristics to evaluate the "optimal" solutions and the number of states examined.
- Provide a visual to show the progression of generated states and optimal solutions
- Modify the program so that the robot needs to move multiple blocks, but can only push one at a time.
- Incorporate variable barriers that may appear while in the process of moving a block, changing the floor plan.
- Describe other realistic extensions to this problem.