liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Admissible Heuristics for Automated Planning
Linköping University, Department of Computer and Information Science, KPLAB - Knowledge Processing Lab. Linköping University, The Institute of Technology.
2006 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

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.

Place, publisher, year, edition, pages
Institutionen för datavetenskap , 2006. , p. 164
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1004
Keywords [en]
AI planning, optimal planning, temporal planning, heuristic search
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-6042ISBN: 91-85497-28-2 (print)OAI: oai:DiVA.org:liu-6042DiVA, id: diva2:21613
Public defence
2006-03-15, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 13:15 (English)
Opponent
Supervisors
Available from: 2006-03-13 Created: 2006-03-13 Last updated: 2023-08-09

Open Access in DiVA

errata(114 kB)213 downloads
File information
File name ERRATA01.pdfFile size 114 kBChecksum SHA-1
d9642b79950cf52219e1b71267cfac6c892e4bdf7818fb1af1054cafbeabc8debc524853
Type errataMimetype application/pdf
fulltext(1473 kB)3796 downloads
File information
File name FULLTEXT01.pdfFile size 1473 kBChecksum SHA-1
9751429865f0893df2e5852f57a32d507b895ae4509999c0bada63363dbf0eb0dafb00df
Type fulltextMimetype application/pdf

Authority records

Haslum, Patrik

Search in DiVA

By author/editor
Haslum, Patrik
By organisation
KPLAB - Knowledge Processing LabThe Institute of Technology
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar
Total: 3809 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 10799 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf