Zoom Link

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 proposal, I will present work on heuristics for 3 different class of problems that commonly appear in industrial settings. The methods in this thesis proposal generally view a region in space-time as a discrete resource, and so a recurring theme in this proposal 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, our proposed procedure outperforms existing methods under constrained settings where a large number of inter-robot Spatio-temporal interactions need to be handled.

We then move on to problems such as 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. In this thesis proposal, 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 close 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.

Building on these results, we propose to carry out further research in two directions. First, we propose to empirically evaluate the benefit of generating cuts through the concurrent use of multiple templates for obtaining tighter lower bounds to the MAPF problem. Second, we propose to investigate the potential of tractable solutions to stochastic variants of the deterministic formulations we considered so far. In particular, we will explore data-driven metrics to assess the quality of a solution, and develop efficient local search heuristics capable of optimizing the data-driven metric.

More Information

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