Homework #2

Avatar Motion Planning

Assigned: October 24, 2007
Due: November 12, 2007

Part 1: Navigating an unknown maze - Bug algorithm

In this assignment, your task is to develop a motion planner for your bot. Your bot will need to be able to both navigate a maze and also walk between points on a map. Note, you do not need to worry about navigation between floors of a building at this point in time.

Getting Started

The minimum requirement for this part is to implement the Bug algorithm. Briefly, one variation of the bug algorithm is as follows:

 
Given a starting point S and a goal G
while Not at G
begin
	while The path to G is not obstructed
	begin
		Move toward the goal
		if the path is obstructed
			Mark the current location p
			Circumnavigate the obstacle until: 
				(a) The robot can move toward G again
				(b) The robot returns to location p (no path) 
		endif 
	end while
end while

The advantage of the bug algorithm is that no explicit knowledge of the environment is required. However, it could potentially take a very long time to reach the goal compared to other methods. Of course, you may also implement any other path planning method discussed in the course.

For ease, you may make a few assumptions. All prims that are walls in the maze will start with the prefix "Comp790Wall". A starting point will be identified by "Comp790Start" and a similarly an end point will be identified by "Comp790Goal". The maze will not cross simulator/region boundaries.

For testing, I have created a simple test maze. It can be found on the Second Floor of the UNC building, or by going here.

Part 2: Motion Planning

In part 2, your task will be to implement a planner that takes the environment into account. Given a problem domain (with fixed boundaries), plan a path from a start to a goal given in local coordinates. It should be able to respond to changes in connectivity of the freespace (through replanning). You do not need to worry about anticipating motion, or localized changes in the environment. There are several possible approaches here:

- Cell decomposition
- Potential field
- Roadmap (PRM, RRT, etc)

Part 3: Exploring Planning in SL (Extra Credit)

After parts 1 and 2, your bot should be able to work in a majority of situations that may arise in Second Life. So, in Part 3 the task will be to explore planning ideas in Second Life. Here are some suggested ideas:

- Planning among many bots
- Coordinated planning of many bots
- Planning among moving prims
- More interesting planning scnearios
- Controlling non-holonomic vehicles
- Propose an idea!

To Turn in

Like last time, I will ask for a copy of your code and also a video which demonstrates how it works.

Motion Planning in Real and Virtual Worlds