We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting 'durative actions' and numerical quantities. These techniques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called 'Temporal Action Graphs' (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.

In particular, modeling context dependent eects, concurrent execution of actions with dierent duration, and continuous resources are all awkward, or impossible, within the STRIPS language. To overcome the rst of these limitations, Pednault (1989) dened the (nowadays widely accepted) ADL language, which amongst other things allows for conditional eects (eects that only occur when their condition holds true in the state of execution). To overcome (one or both of) the latter two limitations, various proposals have been made (e.g., Ghallab & Laruelle, 1994; Koehler, 1998; Smith & Weld, 1999). The most recent eort in this direction is the PDDL2.1 language dened by Fox and Long (2002) as the input language for the 3rd International Planning Competition (IPC-3). The IPC series is a biennial challenge for the planning community, inviting planning systems to participate in a large scale publicly accessible evaluation. IPC-3 was hosted at AIPS-2002, and stressed planning beyond the STRIPS formalism, featuring tracks for temporal and numeric planners. This article describes the approach behind one of the planners that participated in IPC-3, Metric-FF. Metric-FF is an extension of the FF system (that can handle ADL) to numeric constructs.

Jean Morales University College London We study a generalized framework for structured sparsity. It extends the wellknown methods of Lasso and Group Lasso by incorporating additional constraints on the variables as part of a convex optimization problem. This framework provides a straightforward way of favouring prescribed sparsity patterns, such as orderings, contiguous regions and overlapping groups, among others. Existing optimization methods are limited to specific constraint sets and tend to not scale well with sample size and dimensionality. We propose a novel first order proximal method, which builds upon results on fixed points and successive approximations. The algorithm can be applied to a general class of conic and norm constraints sets and relies on a proximity operator subproblem which can be computed explicitly. Experiments on different regression problems demonstrate the efficiency of the optimization algorithm and its scalability with the size of the problem. They also demonstrate state of the art statistical performance, which improves over Lasso and StructOMP.

T oyota T e hnolo gi al Institute at Chi ago 1427 East 60th Str e et, Chi ago IL, 60637 USA Abstra t Au tions are b e oming an in reasingly p opular metho d for transa ting business, esp e-ially o v er the In ternet. This arti le presen ts a general approa h to building autonomous bidding agen ts to bid in m ultiple sim ultaneous au tions for in tera ting go o ds. A ore omp onen t of our approa h learns a mo del of the empiri al pri e dynami s based on past data and uses the mo del to analyti ally al ulate, to the greatest exten t p ossible, optimal bids. W e in tro du e a new and general b o osting-based algorithm for onditional densit y estimation problems of this kind, i.e., sup ervised learning problems in whi h the goal is to estimate the en tire onditional distribution of the real-v alued lab el. This approa h is fully implemen ted as A TT a -2001, a tops oring agen t in the se ond T rading Agen t Comp etition (T A C-01). In an au tion for a single go o d, it is straigh tforw ...

The performance of anytime algorithms can be improved by simultaneously solving several instances of algorithm-problem pairs. These pairs may include different instances of a problem (such as starting from a different initial state), different algorithms (if several alternatives exist), or several runs of the same algorithm (for non-deterministic algorithms). In this paper we present a methodology for designing an optimal scheduling policy based on the statistical characteristics of the algorithms involved. We formally analyze the case where the processes share resources (a single-processor model), and provide an algorithm for optimal scheduling. We analyze, theoretically and empirically, the behavior of our scheduling algorithm for various distribution types.

The automatic generation of decision trees based on off-line reasoning on models of a domain is a reasonable compromise between the advantages of using a model-based approach in technical domains and the constraints imposed by embedded applications. In this paper we extend the approach to deal with temporal information. We introduce a notion of temporal decision tree, which is designed to make use of relevant information as long as it is acquired, and we present an algorithm for compiling such trees from a model-based reasoning system.

TALplanner is a forward-chaining planner that relies on domain knowledge in the shape of temporal logic formulas in order to prune irrelevant parts of the search space. TALplanner recently participated in the third International Planning Competition, which had a clear emphasis on increasing the complexity of the problem domains being used as benchmark tests and the expressivity required to represent these domains in a planning system. Like many other planners, TALplanner had support for some but not all aspects of this increase in expressivity, and a number of changes to the planner were required. After a short introduction to TALplanner, this article describes some of the changes that were made before and during the competition. We also describe the process of introducing suitable domain knowledge for several of the competition domains.

Despite their near dominance, heuristic state search planners still lag behind disjunctive planners in the generation of parallel plans in classical planning. The reason is that directly searching for parallel solutions in state space planners would require the planners to branch on all possible subsets of parallel actions, thus increasing the branching factor exponentially. We present a variant of our heuristic state search planner AltAlt, called AltAltp which generates parallel plans by using greedy online parallelization of partial plans. The greedy approach is significantly informed by the use of novel distance heuristics that AltAltp derives from a graphplan-style planning graph for the problem. While this approach is not guaranteed to provide optimal parallel plans, empirical results show that AltAltp is capable of generating good quality parallel plans at a fraction of the cost incurred by the disjunctive planners.

The recent emergence of heavily-optimized modal decision procedures has highlighted the key role of empirical testing in this domain. Unfortunately, the introduction of extensive empirical tests for modal logics is recent, and so far none of the proposed test generators is very satisfactory. To cope with this fact, we present a new random generation method that provides benefits over previous methods for generating empirical tests. It fixes and much generalizes one of the best-known methods, the random CNF_[]m test, allowing for generating a much wider variety of problems, covering in principle the whole input space. Our new method produces much more suitable test sets for the current generation of modal decision procedures. We analyze the features of the new method by means of an extensive collection of empirical tests.

The success of the Deep Space Remote Agent experiment has demonstrated the promise and importance of metric temporal planning for real-world applications. HSTS/RAX, the planner used in the remote agent experiment, was predicated on the availability of domain-and planner-dependent control knowledge, the collection and maintenance of which is admittedly a laborious and errorprone activity. An obvious question is whether it will be possible to develop domain-independent metric temporal planners that are capable of scaling up to such domains. The past experience has not been particularly encouraging. Although there have been some ambitious attempts-including IxTeT (Ghallab & Laruelle, 1994) and Zeno (Penberthy & Well, 1994), their performance has not been particularly satisfactory. Some encouraging signs however are the recent successes of domain-independent heuristic planning techniques in classical planning (c.f., Nguyen, Kambhampati, & Nigenda, 2001; Bonet, Loerincs, & Geffner, 1997; Hoffmann & Nebel, 2001). Our research is aimed at building on these successes to develop a scalable metric temporal planner. At first blush search control for metric temporal planners would seem to be a very simple matter of adapting the work on heuristic planners in classical planning (Bonet et al., 1997; Nguyen et al., 2001; Hoffmann & Nebel, 2001). The adaptation however does pose several challenges: - Metric temporal planners tend to have significantly larger search spaces than classical planners.