Increasing the Efficiency and Feasibility of Automated Planning through the Specifi cation of Domain-dependent Heuristic Information |
Mikko Berggren Ettienne
|
| Abstract | A* with admissible heuristics is the leading approach to optimal planning. Pattern database (PDB) heuristics are admissible heuristics based on abstractions of the search space and have recently had a breakthrough as general heuristics for automated planning. The selection of appropriate abstractions is of paramount importance to the informedness of a PDB heuristic. Based on a combination of novel and well-known techniques, we show how to efficiently constrain abstractions which leads to increased informedness of PDB heuristics. State-of-theart in PDB heuristics iteratively selects promising abstractions from the search space of all possible abstractions using modi fied local search techniques. We introduce an approach called variable pruned mutex constrained extended pattern database generation that has several theoretical advantages over the state-of-the-art approach. Some of which lead to more informed PDB heuristics, while others lead to reduced computation time without affecting informedness. Experimental evaluations show that our approach also improves state-of-the-art for PDB heuristics in practice. |
| Type | Master's thesis [Academic thesis] |
| Year | 2012 |
| Publisher | Technical University of Denmark, DTU Informatics, E-mail: reception@imm.dtu.dk |
| Address | Asmussens Alle, Building 305, DK-2800 Kgs. Lyngby, Denmark |
| Series | IMM-M.Sc.-2012-137 |
| Note | DTU supervisor: Thomas Bolander, tobo@imm.dtu.dk, DTU Informatics |
| Electronic version(s) | [pdf] |
| Publication link | http://www.imm.dtu.dk/English.aspx |
| BibTeX data | [bibtex] |
| IMM Group(s) | Computer Science & Engineering |