Interval programming: A multi-objective optimization model for autonomous vehicle control

Controlling the behavior of a robot or autonomous vehicle in a stochastic, complex environment is a formidable challenge in artificial intelligence. In stochastic domains, both the current state of the vehicle and the environment are typically reconsidered before deciding each action. If the domain is simple enough, effective plans can be encoded by predetermining the best vehicle action for all possible contingencies, or in all possible vehicle states. In complex environments, particularly with other vehicles, the explosion of possible contingencies or vehicle states prohibits this. In these cases, behavior based architectures are often employed, where each behavior focussed on a specialized vehicle objective. Effective overall vehicle behavior relies heavily on the proper combination, or arbitration, of individual behaviors.; In this work, we present a mathematical programming model, interval programming (IvP), for finding an optimal decision given a set of competing objective functions. We concur with others who believe effective behavior-based action selection involves a multi-objective optimization problem where each behavior contributes a single objective function. To date, such methods have depended on objective functions defined over a sufficiently small discrete decision space as to allow explicit evaluation of all decisions. We believe this is unrealistic in practice and that measures typically taken to sidestep this problem are unacceptable. On the other hand, we also believe that traditional analytical multi-objective optimization methods make demands on objective function form that are unrealistic from the vehicle behavior perspective.; The IvP model strives for a rich balance of speed, flexibility, and accuracy through the use of piecewise linearly defined objective functions. The piece boundaries are typically intervals over decision variables, but may also be intervals over consequences of decision variables coupled with to be blended in each decision. The work here is presented in three parts. First we define the IvP model and show how behaviors create IvP functions with sufficient speed and accuracy. Then we provide a set of algorithms for finding quick, globally optimal solutions to the multi-objective IvP problem using branch and bound techniques. And finally, using an underwater vehicle simulator and a group of core vehicle behaviors, we demonstrate the IvP model on the particularly difficult problem of transiting with other moving, potentially uncooperative, vehicles creating time dependent path obstructions.