Abstract:
Spatio-temporal problems are fairly common in industrial environments. In practice, these problems come with different characteristics and are often very hard to solve optimally. So, practitioners prefer to develop heuristics that exploit mathematical structure specific to the problem for obtaining good performance. In this thesis, we will present work on heuristics for 3 different classes of problems that commonly appear in industrial settings. The methods in this thesis generally view a region in space-time as a discrete resource, and so a recurring theme in this thesis is to view these problems from under a discrete optimization lens.

The first problem we will look at is the Multi-agent path-finding (MAPF) problem. MAPF is a useful abstraction for modeling pick-up and delivery problems within automated warehouses, where conflict-free paths for a set of robots need to be computed from pre-specified start and goal locations for robots while minimizing travel costs. A lot of prior work has been done by AI researchers, predominantly search techniques that are extensions of A* or conflict-driven binary search. Departing from existing approaches, we take a polyhedral view of the problem and propose a cutting plane procedure for computing a lower bound on the optimal solution to the MAPF problem, which is then incorporated into existing search-based methods as an evaluation function via Lagrangians. A novel feature of our approach lies in the cut generation procedure, which we show to be reminiscent of the template matching technique from image processing. Empirically, we show that our procedure outperforms a state-of-the-art search based approach for MAPF.

We then move on to problems such as the movement of products across the factory floor using conveyor belts, railway tracks, etc… At a high level, products need to be transported on railway tracks along a pre-specified route, where each track can appear on the routes for different products, and so each track is like a shared resource. While a product occupies some track, no other product may occupy the same track. The overall objective is to transport all products to their respective destinations in the shortest time (makespan). Such problems are typically abstracted as Blocking Job Shop (BJS) problems. While makespan minimization for BJS is NP-Hard, most local search heuristics for BJS also suffer from a high computational cost per local search move. We propose several algorithmic improvements for existing local search procedures by leveraging structural properties (some existing and some new) of the BJS polytope. With those efficient updates, we are able to achieve new best results on a large fraction of existing BJS benchmark problems.

The third problem deals with situations where robots work in proximity. We present some work done for an aircraft manufacturer, where robots assemble the fuselage of an aircraft. The problem can be abstracted as a multiple-traveling salesman problem with collision and enabling constraints and makespan objective. Collision constraints prohibit robots from occupying certain regions simultaneously. Enabling constraints impose a weak ordering in which robots can perform tasks. We present 2 complementary heuristics which emphasize the routing and scheduling aspects in the problem to different degrees, with both heuristics relying on an efficient implementation of a scheduling sub-solver. We describe the overall system and present empirical results.

More Information

Thesis Committee Members:
Stephen F. Smith, Chair
Willem-Jan van Hoeve
Maxim Likhachev
Christopher J. Beck, University of Toronto