- Accomplishments for the week:
- This week, I made the multiorder algorithm an optimization algorithm- now, it not only finds a satisfactory list of moves such that the robot can deliver all orders on time, but also if finds the path that has the minimum total distance travelled.
- The algorithm uses dynamic programming to find the optimal path. The reason DP works on this problem is because the batch of a orders for a robot is constantly and always decreasing, so we know that the optimal solution for any given robot state is the minimum of all subsequent robot states that come from doing an allowed move + the cost of the action to reach that robot state; therefore, this problem shows very clear optimal substructure. We can base the new algorithm off of that recurrence relation and memoize to never repeat calculations and shave off complexity from a scale of n! to c^n (for some constant c).
- I haven’t done any proof of the complexity yet, but hopefully I can do it at some point this semester.
- This involved creating a hash of the robot state in order to allow for memoization of repeated states, and a modification of the internal function to pass back the optimal path at each subproblem.
- The algorithm uses dynamic programming to find the optimal path. The reason DP works on this problem is because the batch of a orders for a robot is constantly and always decreasing, so we know that the optimal solution for any given robot state is the minimum of all subsequent robot states that come from doing an allowed move + the cost of the action to reach that robot state; therefore, this problem shows very clear optimal substructure. We can base the new algorithm off of that recurrence relation and memoize to never repeat calculations and shave off complexity from a scale of n! to c^n (for some constant c).
- Today I also worked with my team to begin assembly of the robot. We found a Roboclaw ROS Node that provides a wonderful interface for PID low-level controls and encoder odometry on the Roboclaw and its motors, so I got that up and running- we can now send a velocity message to it and the wheel will turn accordingly with the velocity!
- I also worked on inspecting and testing the battery to make sure it was functional and intact with the voltage tester that we bought.
- This week, I made the multiorder algorithm an optimization algorithm- now, it not only finds a satisfactory list of moves such that the robot can deliver all orders on time, but also if finds the path that has the minimum total distance travelled.
- Progress:
- I am currently on-schedule with my tasks.
- Next week’s deliverables:
- Next week, I want to fix a bug we have with our Xavier where it self-reboots seemingly arbitrarily and make sure (rigorously) that the optimization version of the multiorder algorithm is working correctly.
Carnegie Mellon ECE Capstone, Spring 2021 | Michael Li, Sebastian Montiel, Advaith Sethuraman