Brief intro of the project
Mixed Integer Programming (MIP) is a useful approach for many motion planning problems. As its name suggests, MIP is a mathematical optimization problem in which some or all the variables are integers, while the others are continuous variables. For motion planning, the integer variables can be used to describe discrete or logical decisions, such as passing an obstacle on its left or right, while continuous variables can describe the position, orientation or velocities of the robot in some continuous workspace. This projects investigates new MIP formulation for motion planning for single and multiple robots.
Job description / workload
Students’ job includes algorithm development, analysis and experimental verification, which involves developing new formulation of MIP for various motion planning problems, writing code to verify the correctness and runtime efficiency of the new formulations, and comparing the proposed method against the existing formulations. The workload is expected to be at least 12 hours per week.
How many students do you need for this project?
2-3 students.
Keywords of this project
Robotics, Motion Planning, Operation Research, Optimization
Eligibility
Students must finish the following prerequisite task and send the required material to zhongqiang.ren@sjtu.edu.cn to show their capability before joining the project.
Prerequisite: implement the MIP formulation in Sec. III of the following paper using Python and Gurobi solver.
https://rap-lab.github.io/documents/publications/2024_IROS_MTTSP_MICP_Allen_cam.pdf
You should design a few test cases to verify the correctness of your code. You should generate a gif image to show the movement of the robots along the planned path. For your python code, you should provide a toy example in a file with name such as example.py, which can be executed in a terminal window with command: “python3 example.py” and shows the planned results (either in figure or with printed text). If you are not familiar with basic optimization theory, Python, or Gurobi, you need to learn them on your own, which will be the prerequisite for the project. After you finish this task, send (1) your python code (with example.py that is runnable), (2) the gif image you created, together as a zip file to zhongqiang.ren@sjtu.edu.cn for further consideration.
Benefit:
Opportunity to learn, practice, and potentially write an academic paper (if the students work really hard, since paper is never easy).
