Topic: Motion planning of robots Description
This is the final project of the course. The project can be done alone or in a group of at most 4 people. The project contributes to 12% of your total grade. You must use CANVAS to form your own group.
The purpose of this project is to utilize and build upon your knowledge in graph searching algorithms. In robotics, it is common to traverse through rooms or buildings and gather data. To do this the robot traverses through, using graph searching, until it finds the way out. In this project you will be implementing a motion planning algorithm which coordinates the motion of two robots in a room with obstacles. We will consider a room to be consisting of squares, henceforth called spots. The first robot starts at starting point S and has to travel to exit location E. The second robot starts at starting location F and has to travel to exit location L. In the room, a robot can only move at most one spot per movement, which could be north, south, east, west, north-east, north-west, south-east and south-west. This means that a robot can't teleport to other parts of the room. Furthermore, for coordination purposes:
Only one robot moves in one time instant. The two robots may alternate their movements, but they never move simultaneously.
In order to maintain their coordination, they are not allowed to be in the same spot or in spots neighboring each other.
You cannot assume dimensions of the room as each line of the room may be sized differently than other lines. An example input that you should expect will be similar to the sample input file is included below and in CANVAS.
Constraints
The most natural way to implement the project is to view the room as a graph with each square representing a vertex (what are the edges?) If you choose to use this representation, you will develop a graph traversal algorithm which finds a path for the first robot from (S) to (E) and a path for the second robot from (F) to (E) such that the two robots are never in the same spot or in neighboring spot. The constraints of the program include:
1. The program can be written in C. Your program must run on tc.rnet.missouri.edu.
2. Either use a netbeans project or use a Makefile to compile and run the program. Please do not use Visual Studio.
3. Include a README file to tell the TA how to run your program and how to interpret your output.
4. You should include a project report in which you detail your efforts, the algorithms used (along with their complexity) and the contribution of your team members.
5. You may not use any graph theory libraries to solve this program.
6. A moderate amount of error checking and resource management is required. Your application should check that each line from the input file is properly formatted, that the file is successfully opened, the file is successfully closed upon reading of the file and that all allocated space is de-allocated at the exit. If the input is not properly formatted, you should report the error on stdout and exit the program.
7. You may use standard input/output libraries, arrays, vectors, stacks, heaps, lists and queues. If using other libraries, please check with us.
8. A moderate amount of formatting and documentation is required. Comments should be descriptive and used to illustrate the purpose and inner workings of an algorithm or function; they should not be used to annotate each line or self-evident logic.
Input
Your program should take at least one argument on the command line. This argument is the input file to the program. input file itself is formatted as follows. The input file is the floor plan of the room. In the floor plan, each character of the floorplan means:
1. #: Wall or obstacle
2. End of line character and start of line also indicates that you have reached a wall.
3. Space: Empty spot that a robot can move to.
4. S: Starting position of the first robot in the room.
5. E: Exit position of the first robot in the room.
6. F: Starting position of the second robot in the room.
7. L: Exit position of the second robot in the room.