Author name cluster

John L. Bresina

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

4 papers

2 author rows

ICAPS Conference 2005 Conference Paper

Activity Planning for the Mars Exploration Rovers

John L. Bresina
Ari K. Jónsson
Paul H. Morris
Kanna Rajan

Operating the Mars Exploration Rovers is a challenging, time-pressured task. Each day, the operations team must generate a new plan describing the rover activities for the next day. These plans must abide by resource limitations, safety rules, and temporal constraints. The objective is to achieve as much science as possible, choosing from a set of observation requests that oversubscribe rover resources. In order to accomplish this objective, given the short amount of planning time available, the MAPGEN (Mixed-initiative Activity Plan GENerator) system was made a mission-critical part of the ground operations system. MAPGEN is a mixed-initiative system that employs automated constraint-based planning, scheduling, and temporal reasoning to assist operations staff in generating the daily activity plans. This paper describes the adaptation of constraint-based planning and temporal reasoning to a mixed-initiative setting and the key technical solutions developed for the mission deployment of MAPGEN.

Details

UAI Conference 2002 Conference Paper

Planning under Continuous Time and Resource Uncertainty: A Challenge for AI

John L. Bresina
Richard Dearden
Nicolas Meuleau
Sailesh Ramakrishnan
David E. Smith 0001
Richard Washington

We outline a class of problems, typical of Mars rover operations, that are problematic for current methods of planning under uncertainty. The existing methods fail because they suffer from one or more of the following limitations: 1) they rely on very simple models of actions and time, 2) they assume that uncertainty is manifested in discrete action outcomes, 3) they are only practical for very small problems. For many real world problems, these assumptions fail to hold. In particular, when planning the activities for a Mars rover, none of the above assumptions is valid: 1) actions can be concurrent and have differing durations, 2) there is uncertainty concerning action durations and consumption of continuous resources like power, and 3) typical daily plans involve on the order of a hundred actions. This class of problems may be of particular interest to the UAI community because both classical and decision-theoretic planning techniques may be useful in solving it. We describe the rover problem, discuss previous work on planning under uncertainty, and present a detailed, but very small, example illustrating some of the difficulties of finding good plans.

Details

IJCAI Conference 1997 Conference Paper

Automatic Generation of Heuristics for Scheduling

Robert A. Morris
John L. Bresina
Stuart M. Rodgers

This paper presents a technique, called GENH, that automatically generates search heuristics for scheduling problems. The impetus for developing this technique is the growing consensus that heuristics encode advice that is, at best, useful in solving most, or typical, problem instances, and, at worst, useful in solving only a narrowly defined set of instances. In either case, heuristic problem solvers, to be broadly applicable, should have a means of automatically adjusting to the idiosyncrasies of each problem instance. GENH generates a search heuristic for a given problem instance by hillclimbing in the space of possible multi-attribute heuristics, where the evaluation of a candidate heuristic is based on the quality of the solution found under its guidance. We present empirical results obtained by applying GENH to the real world problem of telescope observation scheduling. These results demonstrate that G E N H is a simple and effective way of improving the performance of an heuristic scheduler.

PDF

AAAI Conference 1996 Conference Paper

Heuristic-Biased Stochastic Sampling

John L. Bresina

This paper presents a search technique for scheduling problems, called Heuristic-Biased Stochastic Sampling (HBSS). The underlying assumption behind the HBSS approach is that strictly adhering to a search heuristic often does not yield the best solution and, therefore, exploration off the heuristic path can prove fruitful. Within the HBSS approach, the balance between heuristic adherence and exploration can be controlled according to the confidence one has in the heuristic. By varying this balance, encoded as a bias function, the HBSS approach encompasses a family of search algorithms of which greedy search and completely random search are extreme members. We present empirical results from an application of HBSS to the realworld problem of observation scheduling. These results show that with the proper bias function, it can be easy to outperform greedy search.

PDF Details