Spring2007RobotLabAssignment3 - Revision history

Mgrauer: /* Description of Assignment */

2007-06-04T18:23:11Z

Description of Assignment

Mgrauer: /* Updates */

2007-06-04T18:22:20Z

Updates

Mgrauer: /* Deliverables */

2007-06-01T00:47:14Z

Deliverables

Mgrauer: /* Updates */

2007-05-31T00:25:12Z

Updates

Mgrauer: /* Assignment 3: Path Planning */

2007-05-30T23:48:06Z

Assignment 3: Path Planning

Mgrauer: /* Updates */

2007-05-30T22:36:16Z

Updates

Mgrauer: /* Description of Assignment */

2007-05-30T22:35:38Z

Description of Assignment

Mgrauer: /* Description of Assignment */

2007-05-30T22:34:06Z

Description of Assignment

Mgrauer: /* Assignment 3: Path Planning */

2007-05-30T22:33:49Z

Assignment 3: Path Planning

Mgrauer: /* Assignment 3: Path Planning */

2007-05-30T19:55:40Z

Assignment 3: Path Planning

@@ Line 45: / Line 45: @@
 [[Media:Wavefront_path_map.txt]]
-Finally you will calculate the shortest path from the S to the 2.  Note that this minimal distance path may not be unique.  Your path will replace the S with an A, then increment through alphabet (B..Z, then AA, AB, AC..AZ if needed) with one letter per cell to indicate your path.
+Finally you will calculate the shortest path from the S to the 2.  Note that this minimal distance path may not be unique.  Your path will replace the S with an A, then increment through alphabet (B..Z, then AA, AB, AC..AZ if needed) with one letter per cell to indicate your path.  Since some environments don't allow more than one character in a position, you may start your path over at A, i.e. A-Z, then A-Z again.
 You will turn this step in, so your program should output a file named wavefront_path_plan.txt that looks like the following:

@@ Line 13: / Line 13: @@
 *All parts of the assignment should be done in your code, your code can be whatever language you like
 *The number of rows and columns start from 1, so if rows = 9, then there are 9 rows
 ==== Description of Assignment ====

← Older revision		Revision as of 00:47, 1 June 2007
Line 55:		Line 55:


−	You will be given the ~~path_input~~.txt ~~<SOON TO BE PUT UP>~~ file, and your code should execute on that input file, producing the two output files.	+	You will be given the [[Media:A3_path_input.txt ]] file (and change the name to path_input.txt), and your code should execute on that input file, producing the two output files.

	You should turn in:		You should turn in:

@@ Line 12: / Line 12: @@
 *rows and columns were written backwards, the first number is columns, the second number is rows
 *All parts of the assignment should be done in your code, your code can be whatever language you like
 ==== Description of Assignment ====

← Older revision		Revision as of 23:48, 30 May 2007
Line 11:		Line 11:

	*rows and columns were written backwards, the first number is columns, the second number is rows		*rows and columns were written backwards, the first number is columns, the second number is rows
		+	*All parts of the assignment should be done in your code, your code can be whatever language you like

	==== Description of Assignment ====		==== Description of Assignment ====

@@ Line 10: / Line 10: @@
 ==== Updates ====
-*rows and cols are backwards, I'm currently fixing -Mike
+*rows and columns were written backwards, the first number is columns, the second number is rows
-−
 ==== Description of Assignment ====

@@ Line 22: / Line 22: @@
 Note that this is an example input, which will be followed in the assignment.  The actual input file will be provided below.
-The first line tells how many rows (8), the second line tells how many columns (9) the map has.  The starting point for the path will have an S, and the ending point will have an E.  All obstacles will have a 1, and open cells will have a 0.
+The first line tells how many columns (9), the second line tells how many rows (8) the map has.  The starting point for the path will have an S, and the ending point will have an E.  All obstacles will have a 1, and open cells will have a 0.
 We will assume that your robot can move one square at a time in any direction (up, down, left, right, all four diagonals), as long as it does not go off the map or into an occupied cell.  We also assume that your robot takes up 1 cell.  To provide your robot with a buffer so that it does not run into an obstacle or a wall given the error in its path, you will add extra occupied cells to the map.  You should first increase the size of all obstacles by the size of your robot in all directions by adding a 1 in all directions around all obstacles.

← Older revision		Revision as of 22:33, 30 May 2007
Line 7:		Line 7:
	We will not be using Roombas in this assignment, rather we will simulate a point robot. In this assignment you will write a program to calculate a path through an occupancy map using the Wavefront algorithm, a breadth first search. Once the path has been planned, this turns into a dead reckoning problem, which we have already seen, and since we know how temperamental dead reckoning is, this will introduce a wrinkle. We know with dead reckoning the path your robot takes is not exactly the path you specify, and over the course of the path your robot's error grows. If your robot hits an obstacle, this will throw off the path that you had told your robot to execute and your robot may not finish the course. Before creating the path, your program must first adapt the map so that your robot will not come close to any obstacle or any wall except for the start and end positions. Then you should calculate the possible paths in the map using the Wavefront algorithm, and finally calculate a best path for your robot given the Wavefront map.		We will not be using Roombas in this assignment, rather we will simulate a point robot. In this assignment you will write a program to calculate a path through an occupancy map using the Wavefront algorithm, a breadth first search. Once the path has been planned, this turns into a dead reckoning problem, which we have already seen, and since we know how temperamental dead reckoning is, this will introduce a wrinkle. We know with dead reckoning the path your robot takes is not exactly the path you specify, and over the course of the path your robot's error grows. If your robot hits an obstacle, this will throw off the path that you had told your robot to execute and your robot may not finish the course. Before creating the path, your program must first adapt the map so that your robot will not come close to any obstacle or any wall except for the start and end positions. Then you should calculate the possible paths in the map using the Wavefront algorithm, and finally calculate a best path for your robot given the Wavefront map.

		+
		+	==== Updates ====
		+
		+	*rows and cols are backwards, I'm currently fixing -Mike

← Older revision		Revision as of 19:55, 30 May 2007
Line 5:		Line 5:


−	In this assignment you will write a program to calculate a path through an occupancy map using the Wavefront algorithm, a breadth first search. Once the path has been planned, this turns into a dead reckoning problem, which we have already seen, and since we know how temperamental dead reckoning is, this will introduce a wrinkle. We know with dead reckoning the path your robot takes is not exactly the path you specify, and over the course of the path your robot's error grows. If your robot hits an obstacle, this will throw off the path that you had told your robot to execute and your robot may not finish the course. Before creating the path, your program must first adapt the map so that your robot will not come close to any obstacle or any wall except for the start and end positions. Then you should calculate the possible paths in the map using the Wavefront algorithm, and finally calculate a best path for your robot given the Wavefront map.	+	We will not be using Roombas in this assignment, rather we will simulate a point robot. In this assignment you will write a program to calculate a path through an occupancy map using the Wavefront algorithm, a breadth first search. Once the path has been planned, this turns into a dead reckoning problem, which we have already seen, and since we know how temperamental dead reckoning is, this will introduce a wrinkle. We know with dead reckoning the path your robot takes is not exactly the path you specify, and over the course of the path your robot's error grows. If your robot hits an obstacle, this will throw off the path that you had told your robot to execute and your robot may not finish the course. Before creating the path, your program must first adapt the map so that your robot will not come close to any obstacle or any wall except for the start and end positions. Then you should calculate the possible paths in the map using the Wavefront algorithm, and finally calculate a best path for your robot given the Wavefront map.