A* Graph Search Project - Revision history

Lynch at 07:17, 25 January 2020

2020-01-25T07:17:45Z

Lynch: /* Downloading and testing the needed V-REP files */

2018-07-10T20:12:35Z

Downloading and testing the needed V-REP files

Lynch: /* Writing your program */

2018-07-04T04:51:47Z

Writing your program

Lynch at 22:22, 27 May 2018

2018-05-27T22:22:39Z

Lynch: /* What to submit */

2018-04-10T12:13:39Z

What to submit

Lynch: /* Writing your program */

2018-04-10T12:12:06Z

Writing your program

Lynch: /* What to submit */

2018-04-03T14:05:21Z

What to submit

Lynch: /* What to submit */

2018-04-03T14:04:25Z

What to submit

Lynch: /* What to submit */

2018-04-02T16:54:52Z

What to submit

Lynch: /* What to submit */

2018-04-02T16:54:05Z

What to submit

@@ Line 9: / Line 9: @@
 * 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.
+* The correctness of your CoppeliaSim screenshot of your solution.
-===Downloading and testing the needed V-REP files===
+===Downloading and testing the needed CoppeliaSim files===
-First you should read about the V-REP simulator scene [[V-REP Introduction|"CSV Motion Planning Kilobot"]] (Scene 5) on the Modern Robotics wiki. You should then download the associated .ttt V-REP scene file and the .zip file with sample input to the scene. When you extract the .zip file, you will have a folder with four files inside: nodes.csv (describing the nodes of the graph), edges.csv (describing the edges of the graph), path.csv (describing a solution path), and obstacles.csv (describing cylindrical obstacles, just for visualization purposes). Read the wiki (and the files themselves, which have comments) for more information on the formats of these files.
+First you should read about the CoppeliaSim simulator scene [[CoppeliaSim Introduction|"CSV Motion Planning Kilobot"]] (Scene 5) on the Modern Robotics wiki. You should then download the associated .ttt CoppeliaSim scene file and the .zip file with sample input to the scene. When you extract the .zip file, you will have a folder with four files inside: nodes.csv (describing the nodes of the graph), edges.csv (describing the edges of the graph), path.csv (describing a solution path), and obstacles.csv (describing cylindrical obstacles, just for visualization purposes). Read the wiki (and the files themselves, which have comments) for more information on the formats of these files.
-Play the scene in V-REP and choose the folder with the four files as the input. When you press the "play" button on the interface, you will see a display of the graph, the obstacles, and a path through the graph. You will also see a small mobile robot, a swarm robot called a kilobot, travel along the path. Make sure you can do this before moving on with the rest of the assignment.
+Play the scene in CoppeliaSim and choose the folder with the four files as the input. When you press the "play" button on the interface, you will see a display of the graph, the obstacles, and a path through the graph. You will also see a small mobile robot, a swarm robot called a kilobot, travel along the path. Make sure you can do this before moving on with the rest of the assignment.
-In this assignment, you will create a program that implements A* search to find a minimum-cost path through an undirected graph. You will use the V-REP scene to visualize the graph and the solution path found by your program. ''Although the nodes of your graph are assigned (x,y) coordinates in a plane for visualization purposes (and the solution is animated by a planar mobile robot), the A* graph search you will implement is for fully general undirected weighted graphs.'' As such, the nodes could represent configurations in arbitrary C-spaces, such as the six-dimensional C-space of the rigid chassis of a spacecraft flying among asteroids. We visualize the nodes of the graph as points in a plane, for simplicity.
+In this assignment, you will create a program that implements A* search to find a minimum-cost path through an undirected graph. You will use the CoppeliaSim scene to visualize the graph and the solution path found by your program. ''Although the nodes of your graph are assigned (x,y) coordinates in a plane for visualization purposes (and the solution is animated by a planar mobile robot), the A* graph search you will implement is for fully general undirected weighted graphs.'' As such, the nodes could represent configurations in arbitrary C-spaces, such as the six-dimensional C-space of the rigid chassis of a spacecraft flying among asteroids. We visualize the nodes of the graph as points in a plane, for simplicity.
 ===Writing your program===
@@ Line 37: / Line 37: @@
 indicating that the robot does not go anywhere.
-To see the results of your planner, call the V-REP scene with the nodes.csv and edges.csv file you used as input, the path.csv file that your program wrote as output, and an obstacles.csv file (which is not needed by your program). The obstacles .csv file can be empty if you don't want to visualize obstacles.
+To see the results of your planner, call the CoppeliaSim scene with the nodes.csv and edges.csv file you used as input, the path.csv file that your program wrote as output, and an obstacles.csv file (which is not needed by your program). The obstacles .csv file can be empty if you don't want to visualize obstacles.
 [[Writing_a_CSV_File|'''This page''']] has information on writing csv files in Python, MATLAB, and Mathematica.
@@ Line 57: / Line 57: @@
 #'''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 four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' The nodes.csv file and edges.csv file should be readable by your program. The nodes.csv file should be identical to the sample nodes.csv file you downloaded, except you can delete the comments if your code does not handle files with comments. The edges.csv file should also be identical to the sample edges.csv file (perhaps without the comments) '''except the edge from node 4 to node 7 should be deleted''', to change the graph from the original graph. The obstacles.csv file should be identical to the sample file you downloaded from the wiki. The path.csv file should be the unmodified output of your program when taking nodes.csv and edges.csv as input.
-#'''A V-REP screenshot of your solution path on the graph.'''  The graph among the obstacles should be clearly visible.
+#'''A CoppeliaSim screenshot of your solution path on the graph.'''  The graph among the obstacles should be clearly visible.
 #'''(OPTIONAL) A plain text file called "README.txt" or other explanatory file.''' This has any other information that may help the reviewer understand your submission.

@@ Line 13: / Line 13: @@
 ===Downloading and testing the needed V-REP files===
-First you should read about the V-REP simulator scene [[V-REP Introduction|"CSV Motion Planning Kilobot"]] on the Modern Robotics wiki. You should then download the associated .ttt V-REP scene file and the .zip file with sample input to the scene. When you extract the .zip file, you will have a folder with four files inside: nodes.csv (describing the nodes of the graph), edges.csv (describing the edges of the graph), path.csv (describing a solution path), and obstacles.csv (describing cylindrical obstacles, just for visualization purposes). Read the wiki (and the files themselves, which have comments) for more information on the formats of these files.
+First you should read about the V-REP simulator scene [[V-REP Introduction|"CSV Motion Planning Kilobot"]] (Scene 5) on the Modern Robotics wiki. You should then download the associated .ttt V-REP scene file and the .zip file with sample input to the scene. When you extract the .zip file, you will have a folder with four files inside: nodes.csv (describing the nodes of the graph), edges.csv (describing the edges of the graph), path.csv (describing a solution path), and obstacles.csv (describing cylindrical obstacles, just for visualization purposes). Read the wiki (and the files themselves, which have comments) for more information on the formats of these files.
 Play the scene in V-REP and choose the folder with the four files as the input. When you press the "play" button on the interface, you will see a display of the graph, the obstacles, and a path through the graph. You will also see a small mobile robot, a swarm robot called a kilobot, travel along the path. Make sure you can do this before moving on with the rest of the assignment.

@@ Line 38: / Line 38: @@
 To see the results of your planner, call the V-REP scene with the nodes.csv and edges.csv file you used as input, the path.csv file that your program wrote as output, and an obstacles.csv file (which is not needed by your program). The obstacles .csv file can be empty if you don't want to visualize obstacles.
+[[Writing_a_CSV_File|'''This page''']] has information on writing csv files in Python, MATLAB, and Mathematica.
 ===Data structures, algorithms, and computational efficiency===

@@ Line 1: / Line 1: @@
 This page describes the A* Graph Search Project from the Coursera course "Modern Robotics, Course 4:  Robot Motion Planning and Control."
+[[image:Astar-search.png|right|x200px]]
+===Introduction===
+In this programming assignment, you will implement A* search.  Given a graph, the start node, and the goal node, your program will search the graph for a minimum-cost path from the start to the goal.  Your program will either return a sequence of nodes for a minimum-cost path or indicate that no solution exists.
+Your assignment will be graded based on:
+* 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.
 ===Downloading and testing the needed V-REP files===

@@ Line 44: / Line 44: @@
 #'''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 four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' The nodes.csv file and edges.csv file should be readable by your program. The nodes.csv file should be identical to the sample nodes.csv file you downloaded, except you can delete the comments if your code does not handle files with comments. The edges.csv file should also be identical to the sample edges.csv file (perhaps without the comments) '''except the edge from node 4 to node 7 should be deleted''', to change the graph from the original graph. The obstacles.csv file should be identical to the sample file. The path.csv file should be the unmodified output of your program when taking nodes.csv and edges.csv as input.
+#'''A directory called "results" with four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' The nodes.csv file and edges.csv file should be readable by your program. The nodes.csv file should be identical to the sample nodes.csv file you downloaded, except you can delete the comments if your code does not handle files with comments. The edges.csv file should also be identical to the sample edges.csv file (perhaps without the comments) '''except the edge from node 4 to node 7 should be deleted''', to change the graph from the original graph. The obstacles.csv file should be identical to the sample file you downloaded from the wiki. The path.csv file should be the unmodified output of your program when taking nodes.csv and edges.csv as input.
 #'''A V-REP screenshot of your solution path on the graph.'''  The graph among the obstacles should be clearly visible.
 #'''(OPTIONAL) A plain text file called "README.txt" or other explanatory file.''' This has any other information that may help the reviewer understand your submission.

@@ Line 23: / Line 23: @@
 indicating that the solution path goes from nodes numbered 1, to node2, to node3, etc., finally to N. Your program must find the proper node numbers for node2, node3, etc. The solution path should minimize the sum of the edge costs among all possible paths from node 1 to node N, where the edge costs are given in the edges.csv file. If there is no solution, your output file can be simply
-, 1
 indicating that the robot does not go anywhere.

@@ Line 46: / Line 46: @@
 #'''A directory called "results" with four files in it: nodes.csv, edges.csv, obstacles.csv, and path.csv.''' The nodes.csv file and edges.csv file should be readable by your program. The nodes.csv file should be identical to the sample nodes.csv file you downloaded, except you can delete the comments if your code does not handle files with comments. The edges.csv file should also be identical to the sample edges.csv file (perhaps without the comments) '''except the edge from node 4 to node 7 should be deleted''', to change the graph from the original graph. The obstacles.csv file should be identical to the sample file. The path.csv file should be the unmodified output of your program when taking nodes.csv and edges.csv as input.
 #'''A V-REP video animating your solution path on the graph from the bullet above.''' (See the V-REP description in [https://www.coursera.org/learn/modernrobotics-course1/supplement/MUAaU/v-rep-robot-simulator Week 1 of Course 1], or go directly to [[V-REP Introduction]], to learn about making videos with V-REP.) Your video should be a "reasonable" size (e.g., a few MB, less than 10 MB) and use a standard codec (e.g., some variant of .mp4) that others can view. Your video should be taken from a virtual camera angle that makes it easy to see the graph and kilobot motion.
-#'''(OPTIONAL) A plain text file called "README.txt."''' This has any other information that may help the reviewer understand your submission.
+#'''(OPTIONAL) A plain text file called "README.txt" or other explanatory file.''' This has any other information that may help the reviewer understand your submission.