///Multi-Robot Routing and Scheduling with Spatio-Temporal And Ordering Constraints
Loading Events
This event has passed.

PhD Speaking Qualifier


Jayanth Krishna Mogali PhD Student Robotics Institute,
Carnegie Mellon University
July 30, 2018
1:00 pm
- 2:00 pm
GHC 6501
Multi-Robot Routing and Scheduling with Spatio-Temporal And Ordering Constraints
We consider the problem of allocation and routing a fleet of robots to service a given set of locations while minimizing makespan. The service start times for the locations are subject to AND/OR type precedence constraints. Spatio-temporal constraints prohibit certain states from all feasible schedules where a state is defined as a tuple of robot and it’s location  pairs. In this talk we analyze the sub-problem generated when assignment of locations to the robots and their order of visit has been fixed. We show that it is NP-Complete to determine feasibility and develop an efficient scheduling procedure, both for the sub-problem. We then present two novel makespan minimizing heuristics for the overall problem, the first motivated by  slack based temporal flexibility and the second based on the routing component. We conclude with an anytime procedure for the overall problem and demonstrate results on a real world manufacturing setting.

Stephen Smith
Willem Van Hoeve
Zachary Rubinstein
Chung-Yao Chuang