| 1. |
- Kvarnström, Jonas, 1973-, et al.
(författare)
-
Extending TALplanner with concurrency and resources
- 2000
-
Ingår i: Proceedings of the 14th European Conference on Artificial Intelligence (ECAI). - Amsterdam, The Netherlands : IOS Press. - 4274903885 - 1586030132 ; , s. 501-505
-
Konferensbidrag (refereegranskat)abstract
- We present TALplanner, a forward-chaining planner based on the use of domain-dependent search control knowledge represented as temporal formulas in the Temporal Action Logic (TAL). TAL is a narrative based linear metric time logic used for reasoning about action and change in incompletely specified dynamic environments. TAL is used as the formal semantic basis for TALplanner, where a TAL goal narrative with control formulas is input to TALplanner which then generates a TAL narrative that entails the goal formula. We extend the sequential version of TALplanner, which has previously shown impressive performance on standard benchmarks, in two respects: 1) TALplanner is extended to generate concurrent plans, where operators have varied durations and internal state; and 2) the expressiveness of plan operators is extended for dealing with several different types of resources. The extensions to the planner have been implemented and concurrent planning with resources is demonstrated using an extended logistics benchmark.
|
|
| 2. |
|
|
| 3. |
- Haslum, Patrik, 1973-
(författare)
-
Admissible Heuristics for Automated Planning
- 2006
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The problem of domain-independent automated planning has been a topic of research in Artificial Intelligence since the very beginnings of the field. Due to the desire not to rely on vast quantities of problem specific knowledge, the most widely adopted approach to automated planning is search. The topic of this thesis is the development of methods for achieving effective search control for domain-independent optimal planning through the construction of admissible heuristics. The particular planning problem considered is the so called “classical” AI planning problem, which makes several restricting assumptions. Optimality with respect to two measures of plan cost are considered: in planning with additive cost, the cost of a plan is the sum of the costs of the actions that make up the plan, which are assumed independent, while in planning with time, the cost of a plan is the total execution time – makespan – of the plan. The makespan optimization objective can not, in general, be formulated as a sum of independent action costs and therefore necessitates a problem model slightly different from the classical one. A further small extension to the classical model is made with the introduction of two forms of capacitated resources. Heuristics are developed mainly for regression planning, but based on principles general enough that heuristics for other planning search spaces can be derived on the same basis. The thesis describes a collection of methods, including the hm, additive hm and improved pattern database heuristics, and the relaxed search and boosting techniques for improving heuristics through limited search, and presents two extended experimental analyses of the developed methods, one comparing heuristics for planning with additive cost and the other concerning the relaxed search technique in the context of planning with time, aimed at discovering the characteristics of problem domains that determine the relative effectiveness of the compared methods. Results indicate that some plausible such characteristics have been found, but are not entirely conclusive.
|
|
| 4. |
- Haslum, Patrik, 1973-, et al.
(författare)
-
Domain Knowledge in Planning : Representation and Use
- 2003
-
Ingår i: Proceedings of the ICAPS workshop on PDDL. ; , s. 69-78
-
Konferensbidrag (refereegranskat)abstract
- Planning systems rely on knowledge about the problems they have to solve: The problem description and in many cases advice on how to find a solution. This paper is concerned with a third kind of knowledge which we term domain knowledge: Information about the problem that is produced by one component of the planner and used for advice by another. We first distinguish domain knowledge from the problem description and from advice, and argue for the advantages of the explict use of domain knowledge. Then we identify three classes of domain knowledge for which these advantages are most apparent and define a language, DKEL, to represent these classes. DKEL is designed as an extension to PDDL.
|
|
| 5. |
- Haslum, Patrik, 1973-
(författare)
-
Improving Heuristics Through Search
- 2004
-
Ingår i: Proceedings of the 16th Eureopean Conference on Artificial Intelligence (ECAI). - Amsterdam : IOS Press. - 1586034529 ; , s. 1031-1032
-
Konferensbidrag (refereegranskat)abstract
- We investigate two methods of using limited search to improve admissible heuristics for planning, similar to pattern databases and pattern searches. We also develop a new algorithm for searching AND/OR graphs
|
|
| 6. |
- Haslum, Patrik, 1973-, et al.
(författare)
-
New Admissible Heuristics for Domain-Independent Planning
- 2005
-
Ingår i: Proceedings of the 20th national ´Conference on Artificial Intelligence (AAAI). - : AAAI Press. - 157735236X ; , s. 1163-
-
Konferensbidrag (refereegranskat)abstract
- Admissible heuristics are critical for effective domain-independent planning when optimal solutions must be guaranteed. Two useful heuristics are the hm heuristics, which generalize the reachability heuristic underlying the planning graph, and pattern database heuristics. These heuristics, however, have serious limitations: reachability heuristics capture only the cost of critical paths in a relaxed problem, ignoring the cost of other relevant paths, while PDB heuristics, additive or not, cannot accommodate too many variables in patterns, and methods for automatically selecting patterns that produce good estimates are not known. We introduce two refinements of these heuristics: First, the additive hm heuristic which yields an admissible sum of hm heuristics using a partitioning of the set of actions. Second, the constrained PDB heuristic which uses constraints from the original problem to strengthen the lower bounds obtained from abstractions. The new heuristics depend on the way the actions or problem variables are partitioned. We advance methods for automatically deriving additive hm and PDB heuristics from STRIPS encodings. Evaluation shows improvement over existing heuristics in several domains, although, not surprisingly, no heuristic dominates all the others over all domains.
|
|
