K-Best: A New Method for Real-Time Decision Making

Abstract

Many real-world problems, such as air-traffic control and factory scheduling, require that a sequence of decisions be made in real time. The real-time constraint means that we typically do not have sufficient time to find a complete solution to the problem using traditional methods before we must commit to a decision. We propose an incremental search approach to making real-time, sequential decisions, and then present a new decision method called k-best, which is both an extension of an existing realtime decision method (MINIMIN) and an approximation to a decision-theoretic approach to the real-time decision problem. We next provide an analytical bound on the worst-case expected error when k-best is used instead of the optimal decision method. The averagecase performance of k-best is then compared to MINIMIN on a set of randomly generated problems. Our results show that k-best is an improvement over MINIMIN, although MIN IMIN performs quite well. Given that MIN IMIN is very efficient and easy to implement, we conclude that it should be the algorithm of choice for many real-time decision problems. 1