QuIP: Experimental Design for Expensive Simulators with Many Qualitative Factors via Integer Programming

The need to explore and/or optimize expensive simulators with many qualitative factors arises in broad scientific and engineering problems. Our motivating application lies in path planning – the exploration of feasible paths for navigation – which plays an important role in robotics and assembly planning. For complex settings, the parameter space for path exploration can be discrete and high-dimensional, and the evaluation of path feasibility requires expensive virtual simulations. A carefully selected experimental design is thus essential for timely decision-making. We propose here a novel framework called QuIP, for experimental design of a Gaussian process (GP) surrogate with Qualitative factors via Integer Programming. QuIP leverages a GP surrogate with an exchangeable covariance function. For initial design, we show that its maximin design can be formulated as an assignment problem from operations research, which can be efficiently and globally optimized via state-of-the-art integer programming solvers. For sequential design (specifically, for active learning or black-box optimization), we show that its design problem can similarly be formulated as an assignment problem, which facilitates efficient and reliable optimization with state-of-the-art solvers. We demonstrate the effectiveness of QuIP over existing design methods in a suite of path planning experiments and an application to rover trajectory optimization.