Obstacle World (Search)

Search

Design and implement an agent program to help an autonomous agent navigate an area while avoiding triangular obstacles. The problem description as discovered in class follows.

Performance Measure The agent program will be evaluated based on a combination of the amount of time spent searching for a good path from the start to goal, and the distance actually traveled. To maximize the performance measure, the agent will need to be able to choose the best search strategy to find a good enough path in a short period of time.

Environment The agent is a robot in a 1000 meter by 1000 meter warehouse. The warehouse contains a collection of triangular obstacles.

• The world is fully observable. All of the triangle's corners, the goal location, and the agent location are known at each time step.
• The world is static. The walls, the goal, and the obstacles do not move.
• Each world is solved in a sequential set of steps. But from world to world, the agent's work is episodic.
• The environment is deterministic. GO actions that cause the agent to bump into walls or obstacles will always stop the agent at the collision location. GO actions that exceed the maximum distance per step will be truncated at the maximum. Otherwise all actions are completed as expected.
• The environment time proceeds in discrete steps. Locations are reported by the beacons to .01 meters in distance, and .0001 radians in directions. The agent must be within .1 meters of the goal when the STOP action is issued to qualify as reaching the goal.
• There are no other agents in the environment.

Actuators The agent has the following actions:

• GO direction distance
• STOP

Sensors The agent receives the following percepts

• X number : the x coordinate of the agent's location
• Y number : the y coordinate of the agent's location
• BEACON_A_B direction distance : the direction and distance to triangle A's Bth vertex
• GOAL_X number : the x coordinate of the goal's location
• GOAL_Y number : the y coordinate of the goal's location
• GOAL_VISBABLE T : only set if the goal is directly visible
• BUMP T : only set if the agent bumped into an obstacle last time step

The starter kit is available through anonymous CVS checkout.

saturn$ cvs -d :pserver:anonymous@helios.cs.dixie.edu:/home/cs4300/cvs login
saturn$ cvs -d :pserver:anonymous@helios.cs.dixie.edu:/home/cs4300/cvs co ai ai-agents

The programs of interest are ObstacleCreateWorld, ObstacleDisplay, and OS_Test.