Sampling-Based Planning - Revision history

Lynch at 07:22, 25 January 2020

2020-01-25T07:22:06Z

Lynch: /* Details */

2019-07-15T12:06:14Z

Details

← Older revision		Revision as of 07:06, 15 July 2019
Line 33:		Line 33:
	The start configuration is at (x, y) = (-0.5, -0.5), the bottom left corner of the square environment, and the goal configuration is at (x, y) = (0.5, 0.5), the top right corner of the square environment.		The start configuration is at (x, y) = (-0.5, -0.5), the bottom left corner of the square environment, and the goal configuration is at (x, y) = (0.5, 0.5), the top right corner of the square environment.

	You are responsible for collision checking. Given a straight line segment from (x1, y1) to (x2, y2), you must write your own collision checker to see if the line segment intersects a circle (all the obstacles are circles). This is a fairly simple mathematical exercise. If your solution involves finding the intersection of a line with a circle (there are 0, 1, or 2 intersections), make sure to test if the intersection(s) are within the length of the line segment! A less desirable, but still acceptable, solution could test sample points finely on the line segment between (x1, y1) and (x2, y2).		You are responsible for collision checking. Given a straight line segment from (x1, y1) to (x2, y2), you must write your own collision checker to see if the line segment intersects a circle (all the obstacles are circles). This is a fairly simple mathematical exercise. If your solution involves finding the intersection of a line with a circle (there are 0, 1, or 2 intersections), make sure to test if the intersection(s) are within the length of the line segment! A less desirable, but still acceptable, solution could test sample points finely on the line segment between (x1, y1) and (x2, y2). You should treat the robot as a point; in other words, if the radius of the robot is actually <math>r</math> and the radius of an obstacle is <math>R</math>, you can assume the radius of the robot has been shrunk to 0 and the radius of the obstacle has been grown to <math>R+r</math>.

	Your program should take as input the obstacles.csv file that you created by cutting and pasting the obstacle description above. The output of your program should be three files: nodes.csv, edges.csv, and path.csv. ([[Writing_a_CSV_File\|'''This page''']] has information on writing csv files in Python, MATLAB, and Mathematica.) All of these should be in the format described on the wiki page for the csv motion planning kilobot scene. When you put your input file and your three output files in a directory (named "results," for example), then when you call the V-REP scene with this directory as input, you should see the obstacles, your graph or tree, and the solution path, as well as an animation of the motion.		Your program should take as input the obstacles.csv file that you created by cutting and pasting the obstacle description above. The output of your program should be three files: nodes.csv, edges.csv, and path.csv. ([[Writing_a_CSV_File\|'''This page''']] has information on writing csv files in Python, MATLAB, and Mathematica.) All of these should be in the format described on the wiki page for the csv motion planning kilobot scene. When you put your input file and your three output files in a directory (named "results," for example), then when you call the V-REP scene with this directory as input, you should see the obstacles, your graph or tree, and the solution path, as well as an animation of the motion.

Lynch at 20:13, 10 July 2018

2018-07-10T20:13:05Z

← Older revision		Revision as of 15:13, 10 July 2018
Line 14:		Line 14:
	===Details===		===Details===

	In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.		In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]] (Scene 5). You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.

	[[Media:planning_coursera.zip\|'''You can download the files for this obstacle-cluttered environment in the zipped folder here.''']] Only the obstacles.csv file is relevant, since it is the input to your planner. The other files in the folder, nodes.csv, edges.csv, and path.csv, are placeholders; your program should write these files as output. The information in the obstacles.csv file is also replicated below:		[[Media:planning_coursera.zip\|'''You can download the files for this obstacle-cluttered environment in the zipped folder here.''']] Only the obstacles.csv file is relevant, since it is the input to your planner. The other files in the folder, nodes.csv, edges.csv, and path.csv, are placeholders; your program should write these files as output. The information in the obstacles.csv file is also replicated below:

Lynch: /* Details */

2018-07-04T04:53:12Z

Details

← Older revision		Revision as of 23:53, 3 July 2018
Line 35:		Line 35:
	You are responsible for collision checking. Given a straight line segment from (x1, y1) to (x2, y2), you must write your own collision checker to see if the line segment intersects a circle (all the obstacles are circles). This is a fairly simple mathematical exercise. If your solution involves finding the intersection of a line with a circle (there are 0, 1, or 2 intersections), make sure to test if the intersection(s) are within the length of the line segment! A less desirable, but still acceptable, solution could test sample points finely on the line segment between (x1, y1) and (x2, y2).		You are responsible for collision checking. Given a straight line segment from (x1, y1) to (x2, y2), you must write your own collision checker to see if the line segment intersects a circle (all the obstacles are circles). This is a fairly simple mathematical exercise. If your solution involves finding the intersection of a line with a circle (there are 0, 1, or 2 intersections), make sure to test if the intersection(s) are within the length of the line segment! A less desirable, but still acceptable, solution could test sample points finely on the line segment between (x1, y1) and (x2, y2).

	Your program should take as input the obstacles.csv file that you created by cutting and pasting the obstacle description above. The output of your program should be three files: nodes.csv, edges.csv, and path.csv. All of these should be in the format described on the wiki page for the csv motion planning kilobot scene. When you put your input file and your three output files in a directory (named "results," for example), then when you call the V-REP scene with this directory as input, you should see the obstacles, your graph or tree, and the solution path, as well as an animation of the motion.		Your program should take as input the obstacles.csv file that you created by cutting and pasting the obstacle description above. The output of your program should be three files: nodes.csv, edges.csv, and path.csv. ([[Writing_a_CSV_File\|'''This page''']] has information on writing csv files in Python, MATLAB, and Mathematica.) All of these should be in the format described on the wiki page for the csv motion planning kilobot scene. When you put your input file and your three output files in a directory (named "results," for example), then when you call the V-REP scene with this directory as input, you should see the obstacles, your graph or tree, and the solution path, as well as an animation of the motion.

	You may optionally have another input file, perhaps called "parameters.csv" or "parameters.txt," that contain other input to your motion planner. Examples of such input could be the number of nodes to create in a PRM graph or the likelihood (as a percentage) that an RRT "random" sample is chosen as the goal node (to attempt to complete the motion planning problem).		You may optionally have another input file, perhaps called "parameters.csv" or "parameters.txt," that contain other input to your motion planner. Examples of such input could be the number of nodes to create in a PRM graph or the likelihood (as a percentage) that an RRT "random" sample is chosen as the goal node (to attempt to complete the motion planning problem).
Line 41:		Line 41:
	'''Your program will not be judged on efficiency!''' Ideally you would employ efficient data structures and algorithms to find the nearest nodes to a given configuration, or to check whether a given straight-line path collides with an obstacle. But the point of this assignment is to demonstrate your understanding of the motion planning technique, not to demonstrate mastery of efficient programming, nor to write software that runs quickly on large problems. For example, to find the nearest node to a particular configuration, you could simply calculate the distance to each of the nodes.		'''Your program will not be judged on efficiency!''' Ideally you would employ efficient data structures and algorithms to find the nearest nodes to a given configuration, or to check whether a given straight-line path collides with an obstacle. But the point of this assignment is to demonstrate your understanding of the motion planning technique, not to demonstrate mastery of efficient programming, nor to write software that runs quickly on large problems. For example, to find the nearest node to a particular configuration, you could simply calculate the distance to each of the nodes.

	'''However, your program will be judged on clarity!''' Remember that your code may be reviewed by someone unfamiliar with your programming language. Also, you must write your code modularly with multiple functions. For example, a function for testing whether a path from (x1, y1) to (x2, y2) is in collision with any obstacle could call another function which checks if it is in collision with a specific circular obstacle. This single-obstacle collision-detection function could then call a function that returns the intersection points of a line with a circle, then another function that checks if these intersections (if they exist) belong to the line segment or are on the line containing the line segment but are outside the segment.		'''However, your program will be judged on clarity!''' Remember that your code may be reviewed by someone unfamiliar with your programming language. Also, you must write your code modularly with multiple functions. For example, a function for testing whether a path from (x1, y1) to (x2, y2) is in collision with any obstacle could call another function which checks if it is in collision with a specific circular obstacle. This single-obstacle collision-detection function could then call a function that returns the intersection points of a line with a circle, then another function that checks if these intersections (if they exist) belong to the line segment or are on the line containing the line segment but are outside the segment.

	===If you choose to program an RRT===		===If you choose to program an RRT===

Lynch at 22:31, 27 May 2018

2018-05-27T22:31:22Z

← Older revision		Revision as of 17:31, 27 May 2018
Line 1:		Line 1:
			This page describes the Sampling-Based Planning project from the Coursera course "Modern Robotics, Course 4: Robot Motion Planning and Control."

	[[image:motion_planning_scene.png\|right\|thumb\|x250px\|The environment for motion planning for a point robot moving in the plane.]]		[[image:motion_planning_scene.png\|right\|thumb\|x250px\|The environment for motion planning for a point robot moving in the plane.]]

			===Introduction===
			In this programming assignment, you will implement a sampling-based planner, either an RRT or a PRM, to find a path for a point robot through the cluttered planar environment shown on the right.

			Your project will be graded on:
			* An evaluation of your description of your planner. It will be graded on clarity and completeness.
			* An evaluation of your source code, including its clarity for the reader.
			* The correctness of your code's output, according to the specification below.
			* The correctness of your V-REP screenshot of your solution path on the graph.

			===Details===

	In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.		In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.

Lynch: /* What to submit */

2018-05-13T22:17:03Z

What to submit

← Older revision		Revision as of 17:17, 13 May 2018
Line 55:		Line 55:
	#'''A directory called "results" with (at least) four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' Your results directory should include the obstacles.csv input file as well as output files nodes.csv, edges.csv, and path.csv produced by your planner. These output files must correspond to the screenshot you submit. Your results directory can optionally have another file or files with other input needed by your planner, provided these files are clearly described in the README.		#'''A directory called "results" with (at least) four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' Your results directory should include the obstacles.csv input file as well as output files nodes.csv, edges.csv, and path.csv produced by your planner. These output files must correspond to the screenshot you submit. Your results directory can optionally have another file or files with other input needed by your planner, provided these files are clearly described in the README.
	#'''A V-REP screenshot of your solution path on the graph/tree.''' The graph among the obstacles should be clearly visible.		#'''A V-REP screenshot of your solution path on the graph/tree.''' The graph among the obstacles should be clearly visible.
	#'''(OPTIONAL) A second ~~result~~ folder (e.g., "~~results2~~") with another interesting motion planning problem ~~and~~ its solution.'''		#'''(OPTIONAL) A second results folder (e.g., "results-extra") with another interesting motion planning problem, its solution, and a V-REP screenshot.'''

Lynch: /* What to submit */

2018-05-13T22:16:13Z

What to submit

← Older revision		Revision as of 17:16, 13 May 2018
Line 55:		Line 55:
	#'''A directory called "results" with (at least) four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' Your results directory should include the obstacles.csv input file as well as output files nodes.csv, edges.csv, and path.csv produced by your planner. These output files must correspond to the screenshot you submit. Your results directory can optionally have another file or files with other input needed by your planner, provided these files are clearly described in the README.		#'''A directory called "results" with (at least) four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' Your results directory should include the obstacles.csv input file as well as output files nodes.csv, edges.csv, and path.csv produced by your planner. These output files must correspond to the screenshot you submit. Your results directory can optionally have another file or files with other input needed by your planner, provided these files are clearly described in the README.
	#'''A V-REP screenshot of your solution path on the graph/tree.''' The graph among the obstacles should be clearly visible.		#'''A V-REP screenshot of your solution path on the graph/tree.''' The graph among the obstacles should be clearly visible.
			#'''(OPTIONAL) A second result folder (e.g., "results2") with another interesting motion planning problem and its solution.'''

Lynch at 16:39, 1 May 2018

2018-05-01T16:39:10Z

← Older revision		Revision as of 11:39, 1 May 2018
Line 1:		Line 1:
	[[image:motion_planning_scene.png\|right\|thumb\|x250px\|The environment for motion planning.]]		[[image:motion_planning_scene.png\|right\|thumb\|x250px\|The environment for motion planning for a point robot moving in the plane.]]

	In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.		In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.

Lynch at 16:38, 1 May 2018

2018-05-01T16:38:22Z

← Older revision		Revision as of 11:38, 1 May 2018
Line 1:		Line 1:
	[[image:motion_planning_scene.png\|right\|x250px\|The environment for motion planning.]]		[[image:motion_planning_scene.png\|right\|thumb\|x250px\|The environment for motion planning.]]

	In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.		In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.

Lynch at 16:38, 1 May 2018

2018-05-01T16:38:06Z

← Older revision		Revision as of 11:38, 1 May 2018
Line 1:		Line 1:
	[[image:motion_planning_scene.png\|right\|x250px]]		[[image:motion_planning_scene.png\|right\|x250px\|The environment for motion planning.]]

	In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.		In this assignment you will use the same V-REP visualization scene as in the previous assignment, [[V-REP Introduction\|the csv motion planning kilobot scene]]. You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.

← Older revision		Revision as of 02:22, 25 January 2020
Line 10:		Line 10:
	* An evaluation of your source code, including its clarity for the reader.		* An evaluation of your source code, including its clarity for the reader.
	* The correctness of your code's output, according to the specification below.		* The correctness of your code's output, according to the specification below.
	* The correctness of your ~~V-REP~~ screenshot of your solution path on the graph.		* The correctness of your CoppeliaSim screenshot of your solution path on the graph.

	===Details===		===Details===

	In this assignment you will use the same ~~V-REP~~ visualization scene as in the previous assignment, [[~~V-REP~~ Introduction\|the csv motion planning kilobot scene]] (Scene 5). You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.		In this assignment you will use the same CoppeliaSim visualization scene as in the previous assignment, [[CoppeliaSim Introduction\|the csv motion planning kilobot scene]] (Scene 5). You have the choice of programming either an RRT or a PRM to find a path for a point robot moving in a plane among the obstacles shown in the image at the right.

	[[Media:planning_coursera.zip\|'''You can download the files for this obstacle-cluttered environment in the zipped folder here.''']] Only the obstacles.csv file is relevant, since it is the input to your planner. The other files in the folder, nodes.csv, edges.csv, and path.csv, are placeholders; your program should write these files as output. The information in the obstacles.csv file is also replicated below:		[[Media:planning_coursera.zip\|'''You can download the files for this obstacle-cluttered environment in the zipped folder here.''']] Only the obstacles.csv file is relevant, since it is the input to your planner. The other files in the folder, nodes.csv, edges.csv, and path.csv, are placeholders; your program should write these files as output. The information in the obstacles.csv file is also replicated below:
Line 35:		Line 35:
	You are responsible for collision checking. Given a straight line segment from (x1, y1) to (x2, y2), you must write your own collision checker to see if the line segment intersects a circle (all the obstacles are circles). This is a fairly simple mathematical exercise. If your solution involves finding the intersection of a line with a circle (there are 0, 1, or 2 intersections), make sure to test if the intersection(s) are within the length of the line segment! A less desirable, but still acceptable, solution could test sample points finely on the line segment between (x1, y1) and (x2, y2). You should treat the robot as a point; in other words, if the radius of the robot is actually <math>r</math> and the radius of an obstacle is <math>R</math>, you can assume the radius of the robot has been shrunk to 0 and the radius of the obstacle has been grown to <math>R+r</math>.		You are responsible for collision checking. Given a straight line segment from (x1, y1) to (x2, y2), you must write your own collision checker to see if the line segment intersects a circle (all the obstacles are circles). This is a fairly simple mathematical exercise. If your solution involves finding the intersection of a line with a circle (there are 0, 1, or 2 intersections), make sure to test if the intersection(s) are within the length of the line segment! A less desirable, but still acceptable, solution could test sample points finely on the line segment between (x1, y1) and (x2, y2). You should treat the robot as a point; in other words, if the radius of the robot is actually <math>r</math> and the radius of an obstacle is <math>R</math>, you can assume the radius of the robot has been shrunk to 0 and the radius of the obstacle has been grown to <math>R+r</math>.

	Your program should take as input the obstacles.csv file that you created by cutting and pasting the obstacle description above. The output of your program should be three files: nodes.csv, edges.csv, and path.csv. ([[Writing_a_CSV_File\|'''This page''']] has information on writing csv files in Python, MATLAB, and Mathematica.) All of these should be in the format described on the wiki page for the csv motion planning kilobot scene. When you put your input file and your three output files in a directory (named "results," for example), then when you call the ~~V-REP~~ scene with this directory as input, you should see the obstacles, your graph or tree, and the solution path, as well as an animation of the motion.		Your program should take as input the obstacles.csv file that you created by cutting and pasting the obstacle description above. The output of your program should be three files: nodes.csv, edges.csv, and path.csv. ([[Writing_a_CSV_File\|'''This page''']] has information on writing csv files in Python, MATLAB, and Mathematica.) All of these should be in the format described on the wiki page for the csv motion planning kilobot scene. When you put your input file and your three output files in a directory (named "results," for example), then when you call the CoppeliaSim scene with this directory as input, you should see the obstacles, your graph or tree, and the solution path, as well as an animation of the motion.

	You may optionally have another input file, perhaps called "parameters.csv" or "parameters.txt," that contain other input to your motion planner. Examples of such input could be the number of nodes to create in a PRM graph or the likelihood (as a percentage) that an RRT "random" sample is chosen as the goal node (to attempt to complete the motion planning problem).		You may optionally have another input file, perhaps called "parameters.csv" or "parameters.txt," that contain other input to your motion planner. Examples of such input could be the number of nodes to create in a PRM graph or the likelihood (as a percentage) that an RRT "random" sample is chosen as the goal node (to attempt to complete the motion planning problem).
Line 67:		Line 67:
	#'''Your commented code in a directory called "code."''' Your code should be lightly commented, so it is clear to the reader what the code is doing. No need to go overboard, but keep in mind your reviewer may not be fluent in your programming language. Your code comments must include an example of how to use the code. You can write your program in any language, provided it is clearly structured, reasonably modular, easy to understand for a reader with no experience in your programming language, and with sufficient comments. Your program can span multiple files, or it can be a single file, if appropriate. If your code is in Mathematica, turn in (a) your .nb notebook file and (b) a .pdf printout of your code, so a reviewer can read your code without having to have the Mathematica software.		#'''Your commented code in a directory called "code."''' Your code should be lightly commented, so it is clear to the reader what the code is doing. No need to go overboard, but keep in mind your reviewer may not be fluent in your programming language. Your code comments must include an example of how to use the code. You can write your program in any language, provided it is clearly structured, reasonably modular, easy to understand for a reader with no experience in your programming language, and with sufficient comments. Your program can span multiple files, or it can be a single file, if appropriate. If your code is in Mathematica, turn in (a) your .nb notebook file and (b) a .pdf printout of your code, so a reviewer can read your code without having to have the Mathematica software.
	#'''A directory called "results" with (at least) four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' Your results directory should include the obstacles.csv input file as well as output files nodes.csv, edges.csv, and path.csv produced by your planner. These output files must correspond to the screenshot you submit. Your results directory can optionally have another file or files with other input needed by your planner, provided these files are clearly described in the README.		#'''A directory called "results" with (at least) four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' Your results directory should include the obstacles.csv input file as well as output files nodes.csv, edges.csv, and path.csv produced by your planner. These output files must correspond to the screenshot you submit. Your results directory can optionally have another file or files with other input needed by your planner, provided these files are clearly described in the README.
	#'''A ~~V-REP~~ screenshot of your solution path on the graph/tree.''' The graph among the obstacles should be clearly visible.		#'''A CoppeliaSim screenshot of your solution path on the graph/tree.''' The graph among the obstacles should be clearly visible.
	#'''(OPTIONAL) A second results folder (e.g., "results-extra") with another interesting motion planning problem, its solution, and a ~~V-REP~~ screenshot.'''		#'''(OPTIONAL) A second results folder (e.g., "results-extra") with another interesting motion planning problem, its solution, and a CoppeliaSim screenshot.'''