Simplifying a Lifted Plan Graph Using Domain Splitting
Image process planning, lifted plan graph and induced CSP splitting states and actions in lifted plan graph enables improved arc consistency in underlying CSP.
Petrie, Karen↗
Engineering topics
Frank, Jeremy
Publications and source records attributed to Frank, Jeremy.
Planning and Scheduling for Fleets of Earth Observing Satellites
We address the problem of scheduling observations for a collection of earth observing satellites. This scheduling task is a difficult optimization problem, potentially involving many satellites, hundreds of requests, constraints on when and how to service each request, and resources such as instruments, recording devices, transmitters, and ground stations. High-fidelity models are required to ensure the validity of schedules; at the same time, the size and complexity of the problem makes it unlikely that systematic optimization search methods will be able to solve them in a reasonable time. This paper presents a constraint-based approach to solving the Earth Observing Satellites (EOS) scheduling problem, and proposes a stochastic heuristic search method for solving it.
Frank, Jeremy↗
Propagating Resource Constraints Using Mutual Exclusion Reasoning
One of the most recent techniques for propagating resource constraints in Constraint Based scheduling is Energy Constraint. This technique focuses in precedence based scheduling, where precedence relations are taken into account rather than the absolute position of activities. Although, this particular technique proved to be efficient on discrete unary resources, it provides only loose bounds for jobs using discrete multi-capacity resources. In this paper we show how mutual exclusion reasoning can be used to propagate time bounds for activities using discrete resources. We show that our technique based on critical path analysis and mutex reasoning is just as effective on unary resources, and also shows that it is more effective on multi-capacity resources, through both examples and empirical study.
Frank, Jeremy↗
A Constraint-based Attribute and Interval Planning
In this paper we introduce Constraint-based Attribute and Interval Planning (CAIP), a new paradigm for representing and reasoning about plans. The paradigm enables the description of planning domains with time, resources, concurrent activities, mutual exclusions among sets of activities, disjunctive preconditions and conditional effects. We provide a theoretical foundation for the paradigm using a mapping to first order logic. We also show that CAIP plans are naturally expressed by networks of constraints, and that planning maps directly to dynamic constraint reasoning. In addition, we show how constraint templates are used to provide a compact mechanism for describing planning domains.
Frank, Jeremy↗
Bridging the Gap Between Planning and Scheduling
Planning research in Artificial Intelligence (AI) has often focused on problems where there are cascading levels of action choice and complex interactions between actions. In contrast. Scheduling research has focused on much larger problems where there is little action choice, but the resulting ordering problem is hard. In this paper, we give an overview of M planning and scheduling techniques, focusing on their similarities, differences, and limitations. We also argue that many difficult practical problems lie somewhere between planning and scheduling, and that neither area has the right set of tools for solving these vexing problems.
Smith, David E.↗
Generalizing Backtrack-Free Search: A Framework for Search-Free Constraint Satisfaction
Tractable classes of constraint satisfaction problems are of great importance in artificial intelligence. Identifying and taking advantage of such classes can significantly speed up constraint problem solving. In addition, tractable classes are utilized in applications where strict worst-case performance guarantees are required, such as constraint-based plan execution. In this work, we present a formal framework for search-free (backtrack-free) constraint satisfaction. The framework is based on general procedures, rather than specific propagation techniques, and thus generalizes existing techniques in this area. We also relate search-free problem solving to the notion of decision sets and use the result to provide a constructive criterion that is sufficient to guarantee search-free problem solving.
Jonsson, Ari K.↗
On Reformulating Planning as Dynamic Constraint Satisfaction
In recent years, researchers have reformulated STRIPS planning problems as SAT problems or CSPs. In this paper, we discuss the Constraint-Based Interval Planning (CBIP) paradigm, which can represent planning problems incorporating interval time and resources. We describe how to reformulate mutual exclusion constraints for a CBIP-based system, the Extendible Uniform Remote Operations Planner Architecture (EUROPA). We show that reformulations involving dynamic variable domains restrict the algorithms which can be used to solve the resulting DCSP. We present an alternative formulation which does not employ dynamic domains, and describe the relative merits of the different reformulations.
Frank, Jeremy↗
SOFIA's Choice: Automating the Scheduling of Airborne Observations
This paper describes the problem of scheduling observations for an airborne telescope. Given a set of prioritized observations to choose from, and a wide range of complex constraints governing legitimate choices and orderings, how can we efficiently and effectively create a valid flight plan which supports high priority observations? This problem is quite different from scheduling problems which are routinely solved automatically in industry. For instance, the problem requires making choices which lead to other choices later, and contains many interacting complex constraints over both discrete and continuous variables. Furthermore, new types of constraints may be added as the fundamental problem changes. As a result of these features, this problem cannot be solved by traditional scheduling techniques. The problem resembles other problems in NASA and industry, from observation scheduling for rovers and other science instruments to vehicle routing. The remainder of the paper is organized as follows. In 2 we describe the observatory in order to provide some background. In 3 we describe the problem of scheduling a single flight. In 4 we compare flight planning and other scheduling problems and argue that traditional techniques are not sufficient to solve this problem. We also mention similar complex scheduling problems which may benefit from efforts to solve this problem. In 5 we describe an approach for solving this problem based on research into a similar problem, that of scheduling observations for a space-borne probe. In 6 we discuss extensions of the flight planning problem as well as other problems which are similar to flight planning. In 7 we conclude and discuss future work.
Frank, Jeremy↗
Using Collective Intelligence to Route Internet Traffic
A Collective Intelligence (COIN) is a community of interacting reinforcement learning (RL) algorithms designed so that their collective behavior maximizes a global utility function. We introduce the theory of COINs, then present experiments using that theory to design COINs to control internet traffic routing. These experiments indicate that COINs outperform previous RL-based systems for such routing that have previously been investigated.
Wolpert, David H.↗
When Gravity Fails: Local Search Topology
Local search algorithms for combinatorial search problems frequently encounter a sequence of states in which it is impossible to improve the value of the objective function; moves through these regions, called {\em plateau moves), dominate the time spent in local search. We analyze and characterize {\em plateaus) for three different classes of randomly generated Boolean Satisfiability problems. We identify several interesting features of plateaus that impact the performance of local search algorithms. We show that local minima tend to be small but occasionally may be very large. We also show that local minima can be escaped without unsatisfying a large number of clauses, but that systematically searching for an escape route may be computationally expensive if the local minimum is large. We show that plateaus with exits, called benches, tend to be much larger than minima, and that some benches have very few exit states which local search can use to escape. We show that the solutions (i.e. global minima) of randomly generated problem instances form clusters, which behave similarly to local minima. We revisit several enhancements of local search algorithms and explain their performance in light of our results. Finally we discuss strategies for creating the next generation of local search algorithms.
Frank, Jeremy↗
Athena: Advanced air launched space booster
The infrastructure for routine, reliable, and inexpensive access of space is a goal that has been actively pursued over the past 50 years, but has yet not been realized. Current launch systems utilize ground launching facilities which require the booster vehicle to plow up through the dense lower atmosphere before reaching space. An air launched system on the other hand has the advantage of being launched from a carrier aircraft above this dense portion of the atmosphere and hence can be smaller and lighter compared to its ground based counterpart. The goal of last year's Aerospace Engineering Course 483 (AE 483) was to design a 227,272 kg (500,000 lb.) air launched space booster which would beat the customer's launch cost on existing launch vehicles by at least 50 percent. While the cost analysis conducted by the class showed that this goal could be met, the cost and size of the carrier aircraft make it appear dubious that any private company would be willing to invest in such a project. To avoid this potential pitfall, this year's AE 483 class was to design as large an air launched space booster as possible which can be launched from an existing or modification to an existing aircraft. An initial estimate of the weight of the booster is 136,363 kg (300,000 lb.) to 159,091 kg (350,000 lb.).
Booker, Corey G.↗