Lab 5 - Path Planning

Lab TAs

Atulya Ravishankar

Jiaqi Zou

Goal

• Given a start pose and end pose, plan and execute a path through a known man without touching any obstacles

picture from ieeexplore.ieee.org

Procedure

1. Choose a reference point on your robot (all measurements will be made with respect to that point).
2. You will be given a start position and an end position (x1, y1), (x2, y2)
1. E.g. “You starting position is (40, 32) and goal is (16, 8)”
3. Your robot will initially be oriented in the positive-y direction.
4. Run path planning algorithm to determine path to be taken (show TAs before robot moves).
• This does not have to be done in RobotC/on the brick. You may use Python, MATLAB or any other tools to generate your trajectory.
5. Your robot will navigate from the given start pose to the end position within specified time limits.
6. You will be graded based on how far away (L2 distance) you are from the goal and how long you take to get there.
7. If your robot leaves the map/hits an obstacle, you will be penalized (refer to grading sheet).
8. There will be an Individual Q & A section at the end of the demo.

The Courses

Hard Course

Easy Course

Insert picture of easy course here

Insert picture of hard course here

Obstacle Locations (inches)

Easy Course

• (12, 24) → (24, 18)
• (33, 18) → (39, 12)

Hard Course

• (0, 24) → (21.3, 36)
• (25.5, 27.5) → (25.5, 18.6)
• (31.5, 36) → (50.6, 22.5)
• (54, 42) → (60, 36)

• Each pair on the left corresponds to opposite corners of an obstacle area
• Coordinates are given in (x, y) form
• Origin is at top-left corner of each course
• Positive-x is to the right
• Positive-y is to the bottom
• Your robot’s initial orientation will be in the positive-y direction

​

All coordinates are in inches and are approximate. You are responsible for measuring their locations yourselves to be sure.

Displaying Your Path

• You must show TAs the intended path/trajectory before your robot moves
• Your path must be easily understandable for TAs during the demo
• Ex: If you used waypoints, you can bring a hard copy of a map with waypoints marked on it.
• Showing the TAs a list of points that the robot will follow is a valid way of showing an intended path
• You could generate a map with the clearly identifiable path displayed on it using tools like Matlab or Python
• If you choose Matlab in conjunction with RobotC, please be sure to practice interfacing between Matlab and RobotC by demo day (given very limited demo time)
• Time taken to calculate path will be part of your 10 minute demo slot.
• You will need to calculate and show the path for each of the two trials.

Path Planning Algorithm

• Choose any algorithm you want!
• Bug 1 / Bug 2
• Wavefront
• Potential function
• Graph Search algorithms
• Anything else you see fit
• You may generate your path externally (MATLAB, Python, NXT, other)
• You cannot use any built-in graph search functions or packages that trivialize this for you
• Make sure every member of the group knows why you picked your algorithm and the trade-offs and challenges associated with this decision.

Individual Q & A

At the end of your team’s demo, we will ask each member of your group one question (3 total questions) that can be related to any of the following:

• General path planning algorithms
• Your team’s implementation for the lab
• The trade-offs your team made when implementing your algorithm
• Real-world path planning

MAKE SURE you fully understand every aspect of your team’s implementation before the demo.

You will NOT be allowed to consult with your teammates when we ask you a question.

Grading

​

Link to Rubric here.

(*Please have a copy printed before demo)

​

*You have 2 trials in total and it is your choice

to decide which course you want to spend it on.

​

Key Regulations

• The obstacles are assumed to be infinitely tall
• No part of your robot can hover over the top of the obstacles regardless of how tall they are in the real world.
• Your demo stops when your robot stops
• Your L2 error will be calculated from the position of your robot at the time the trial was stopped.
• You may not prematurely stop your robot while it is completing its path
• We will give you start/end points using the axes convention outlined earlier.
• If you are using a different convention, it is your responsibility to convert what we give you to what you actually need.
• You must bring your grading sheet to the demo. Teams without grading sheets will not be allowed to demo.
• There is NO video demo submission so please plan accordingly.

Tips

• Start early!
• Consider what constitutes the optimal path
• “Optimal with respect to what?”
• Speed vs. Safety vs. Accuracy
• Define a good C-Space before you start doing path planning
• This will be affected by your robot size. Build with this in mind.
• Be sure you know where is the origin of your C-space
• Take time to tune your dead-reckoning properly
• Think about mechanical changes that can give you an advantage

• Choose your algorithm carefully
• Ease of implementation
• Quality of solution
• Reliability
• Practice the demo procedure before your demo!
• Ensure that the path you calculated can be easily ported into RobotC
• Be prepared to answer questions at the end of your demo
• Hitting an obstacle will severely hurt your chances of successfully completing a path.
• Your code from Lab 3 (Runge Kutta) with PID incorporated into it will be useful for this lab.

​

Questions?