Engineering topics

Minton, Steven

Publications and source records attributed to Minton, Steven.

3 records

NASA NTRS1992

An extended abstract: A heuristic repair method for constraint-satisfaction and scheduling problems

The work described in this paper was inspired by a surprisingly effective neural network developed for scheduling astronomical observations on the Hubble Space Telescope. Our heuristic constraint satisfaction problem (CSP) method was distilled from an analysis of the network. In the process of carrying out the analysis, we discovered that the effectiveness of the network has little to do with its connectionist implementation. Furthermore, the ideas employed in the network can be implemented very efficiently within a symbolic CSP framework. The symbolic implementation is extremely simple. It also has the advantage that several different search strategies can be employed, although we have found that hill-climbing methods are particularly well-suited for the applications that we have investigated. We begin the paper with a brief review of the neural network. Following this, we describe our symbolic method for heuristic repair.

Minton, Steven↗

NASA NTRS1991

An analysis of commitment strategies in planning: The details

We compare the utility of different commitment strategies in planning. Under a 'least commitment strategy', plans are represented as partial orders and operators are ordered only when interactions are detected. We investigate claims of the inherent advantages of planning with partial orders, as compared to planning with total orders. By focusing our analysis on the issue of operator ordering commitment, we are able to carry out a rigorous comparative analysis of two planners. We show that partial-order planning can be more efficient than total-order planning, but we also show that this is not necessarily so.

Minton, Steven↗

NASA NTRS1991

The min-conflicts heuristic: Experimental and theoretical results

This paper describes a simple heuristic method for solving large-scale constraint satisfaction and scheduling problems. Given an initial assignment for the variables in a problem, the method operates by searching through the space of possible repairs. The search is guided by an ordering heuristic, the min-conflicts heuristic, that attempts to minimize the number of constraint violations after each step. We demonstrate empirically that the method performs orders of magnitude better than traditional backtracking techniques on certain standard problems. For example, the one million queens problem can be solved rapidly using our approach. We also describe practical scheduling applications where the method has been successfully applied. A theoretical analysis is presented to explain why the method works so well on certain types of problems and to predict when it is likely to be most effective.

Minton, Steven↗