Publications

Planning models are usually defined in lifted, i.e. first order formalisms, while most solvers need (variable-free) grounded representations. Though techniques for grounding prune unnecessary parts of the model, grounding might – nevertheless – be prohibitively expensive in terms of runtime. To overcome this issue, there has been renewed interest in solving planning problems based on the lifted representation in the last years. While these approaches are based on (heuristic) search, we present an encoding of lifted classical planning in propositional logic and use SAT solvers to solve it. Our evaluation shows that our approach is competitive with the heuristic search-based approaches in satisficing planning and outperforms them in a (length-)optimal setting.

• https://ojs.aaai.org/index.php/ICAPS/article/view/19794

@inproceedings{HoellerB22,
title = {Encoding Lifted Classical Planning in Propositional Logic},
author = {Daniel H{\"o}ller and Gregor Behnke},
url = {https://ojs.aaai.org/index.php/ICAPS/article/view/19794},
year = {2022},
date = {2022},
booktitle = {Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS)},
pages = {134-144},
publisher = {AAAI Press},
abstract = {Planning models are usually defined in lifted, i.e. first order formalisms, while most solvers need (variable-free) grounded representations. Though techniques for grounding prune unnecessary parts of the model, grounding might – nevertheless – be prohibitively expensive in terms of runtime. To overcome this issue, there has been renewed interest in solving planning problems based on the lifted representation in the last years. While these approaches are based on (heuristic) search, we present an encoding of lifted classical planning in propositional logic and use SAT solvers to solve it. Our evaluation shows that our approach is competitive with the heuristic search-based approaches in satisficing planning and outperforms them in a (length-)optimal setting.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

Plan Verification is the task of deciding whether a sequence of actions is a solution for a given planning problem. In HTN planning, the task is computationally expensive and may be up to NP-hard. However, there are situations where it needs to be solved, e.g. when a solution is post-processed, in systems using approximation, or just to validate whether a planning system works correctly (e.g. for debugging or in a competition). There are verification systems based on translations to propositional logic and on techniques from parsing. Here we present a third approach and translate HTN plan verification problems into HTN planning problems. These can be solved using any HTN planning system. We collected a new bench-mark set based on models and results of the 2020 International Planning Competition. Our evaluation shows that our compilation outperforms the approaches from the literature.

• 19795-Article Text-23808-1-2-20220613     (0.39MB)
• https://ojs.aaai.org/index.php/ICAPS/article/view/19795/19554
• https://doi.org/10.1609/icaps.v32i1.19795

@inproceedings{Höller_Wichlacz_Bercher_Behnke_2022,
title = {Compiling HTN Plan Verification Problems into HTN Planning Problems},
author = {Daniel H{\"o}ller and Julia Wichlacz and Pascal Bercher and Gregor Behnke},
url = {https://ojs.aaai.org/index.php/ICAPS/article/view/19795/19554},
doi = {https://doi.org/10.1609/icaps.v32i1.19795},
year = {2022},
date = {2022},
booktitle = {Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS2022)},
pages = {145-150},
abstract = {Plan Verification is the task of deciding whether a sequence of actions is a solution for a given planning problem. In HTN planning, the task is computationally expensive and may be up to NP-hard. However, there are situations where it needs to be solved, e.g. when a solution is post-processed, in systems using approximation, or just to validate whether a planning system works correctly (e.g. for debugging or in a competition). There are verification systems based on translations to propositional logic and on techniques from parsing. Here we present a third approach and translate HTN plan verification problems into HTN planning problems. These can be solved using any HTN planning system. We collected a new bench-mark set based on models and results of the 2020 International Planning Competition. Our evaluation shows that our compilation outperforms the approaches from the literature.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

While state-of-the-art planning systems need a grounded (propositional) task representation, the input model is provided “lifted”, specifying predicates and action schemas with variables over a finite object universe. The size of the grounded model is exponential in predicate/action-schema arity, limiting applicability to cases where it is small enough. Recent work has taken up this challenge, devising an effective lifted forward search planner as basis for lifted heuristic search, as well as a variety of lifted heuristic functions based on the delete relaxation. Here we add a novel family of lifted heuristic functions, based on landmarks. We design two methods for landmark extraction in the lifted setting. The resulting heuristics exhibit performance advantages over previous heuristics in several benchmark domains. Especially the combination with lifted delete relaxation heuristics to a LAMA-style planner yields good results, beating the previous state of the art in lifted planning.

• Landmark-Heuristics-for-Lifted-Classical-Planning     (0.2MB)
• https://doi.org/10.24963/ijcai.2022/647
• https://doi.org/10.24963/ijcai.2022/647

@inproceedings{ijcai2022p647,
title = {Landmark Heuristics for Lifted Classical Planning},
author = {Julia Wichlacz and Daniel H{\"o}ller and J{\"o}rg Hoffmann},
editor = {Lud De Raedt},
url = {https://doi.org/10.24963/ijcai.2022/647},
doi = {https://doi.org/10.24963/ijcai.2022/647},
year = {2022},
date = {2022},
booktitle = {Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22), Vienna, 23-29 July 2022},
pages = {4665-4671},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
abstract = {While state-of-the-art planning systems need a grounded (propositional) task representation, the input model is provided “lifted”, specifying predicates and action schemas with variables over a finite object universe. The size of the grounded model is exponential in predicate/action-schema arity, limiting applicability to cases where it is small enough. Recent work has taken up this challenge, devising an effective lifted forward search planner as basis for lifted heuristic search, as well as a variety of lifted heuristic functions based on the delete relaxation. Here we add a novel family of lifted heuristic functions, based on landmarks. We design two methods for landmark extraction in the lifted setting. The resulting heuristics exhibit performance advantages over previous heuristics in several benchmark domains. Especially the combination with lifted delete relaxation heuristics to a LAMA-style planner yields good results, beating the previous state of the art in lifted planning.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

Recipe texts are an idiosyncratic form of instructional language that pose unique challenges for automatic understanding. One challenge is that a cooking step in one recipe can be explained in another recipe in different words, at a different level of abstraction, or not at all. Previous work has annotated correspondences between recipe instructions at the sentence level, often glossing over important correspondences between cooking steps across recipes. We present a novel and fully-parsed English recipe corpus, ARA (Aligned Recipe Actions), which annotates correspondences between individual actions across similar recipes with the goal of capturing information implicit for accurate recipe understanding. We represent this information in the form of recipe graphs, and we train a neural model for predicting correspondences on ARA. We find that substantial gains in accuracy can be obtained by taking fine-grained structural information about the recipes into account.

• https://aclanthology.org/2021.emnlp-main.554

@inproceedings{donatelli21:align,
title = {Aligning Actions Across Recipe Graphs},
author = {Lucia Donatelli and Theresa Schmidt and Debanjali Biswas and Arne K{\"o}hn and Fangzhou Zhai and Alexander Koller},
url = {https://aclanthology.org/2021.emnlp-main.554},
year = {2021},
date = {2021},
booktitle = {Proceedings of EMNLP},
pages = {6930–6942},
abstract = {Recipe texts are an idiosyncratic form of instructional language that pose unique challenges for automatic understanding. One challenge is that a cooking step in one recipe can be explained in another recipe in different words, at a different level of abstraction, or not at all. Previous work has annotated correspondences between recipe instructions at the sentence level, often glossing over important correspondences between cooking steps across recipes. We present a novel and fully-parsed English recipe corpus, ARA (Aligned Recipe Actions), which annotates correspondences between individual actions across similar recipes with the goal of capturing information implicit for accurate recipe understanding. We represent this information in the form of recipe graphs, and we train a neural model for predicting correspondences on ARA. We find that substantial gains in accuracy can be obtained by taking fine-grained structural information about the recipes into account.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

During the last years, much progress has been made in hierarchical planning towards domain-independent systems that come with sophisticated techniques to solve planning problems instead of relying on advice in the input model. Several of these novel methods have been integrated into the PANDA framework, which is a software system to reason about hierarchical planning tasks. Besides solvers for planning problems based on plan space search, progression search, and translation to propositional logic, it also includes techniques for related problems like plan repair, plan and goal recognition, or plan verifcation. These various techniques share a common infrastructure, like e.g. a standard input language or components for grounding and reachability analysis. This article gives an overview over the PANDA framework, introduces the basic techniques from a high level perspective, and surveys the literature describing the diverse components in detail.

• Höller2021_Article_ThePANDAFrameworkForHierarchic     (0.6MB)
• https://link.springer.com/article/10.1007/s13218-020-00699-y
• https://doi.org/10.1007/s13218-020-00699-y

@article{hoeller-etal-21-PANDA,
title = {The PANDA Framework for Hierarchical Planning},
author = {Daniel H{\"o}ller and Gregor Behnke and Pascal Bercher and Susanne Biundo},
url = {https://link.springer.com/article/10.1007/s13218-020-00699-y},
doi = {https://doi.org/10.1007/s13218-020-00699-y},
year = {2021},
date = {2021},
journal = {K{\"u}nstliche Intelligenz},
abstract = {During the last years, much progress has been made in hierarchical planning towards domain-independent systems that come with sophisticated techniques to solve planning problems instead of relying on advice in the input model. Several of these novel methods have been integrated into the PANDA framework, which is a software system to reason about hierarchical planning tasks. Besides solvers for planning problems based on plan space search, progression search, and translation to propositional logic, it also includes techniques for related problems like plan repair, plan and goal recognition, or plan verifcation. These various techniques share a common infrastructure, like e.g. a standard input language or components for grounding and reachability analysis. This article gives an overview over the PANDA framework, introduces the basic techniques from a high level perspective, and surveys the literature describing the diverse components in detail.},
pubstate = {published},
type = {article}
}

Copy BibTeX to Clipboard

Landmarks (LMs) are state features that need to be made true or tasks that need to be contained in every solution of a planning problem. They are a valuable source of information in planning and can be exploited in various ways. LMs have been used both in classical and hierarchical planning, but while there is much work in classical planning, the techniques in hierarchical planning are less evolved. We introduce a novel LM generation method for Hierarchical Task Network (HTN) planning and show that it is sound and incomplete. We show that every complete approach is as hard as the co-class of the underlying HTN problem, i.e. coNP-hard for our setting (while our approach is in P). On a widely used benchmark set, our approach finds more than twice the number of landmarks than the approach from the literature. Though our focus is on LM generation, we show that the newly discovered landmarks bear information beneficial for solvers.

• 17405-Article Text-20899-1-2-20210518     (0.22MB)
• https://ojs.aaai.org/index.php/AAAI/article/view/17405
• https://doi.org/10.1609/aaai.v35i13.17405

@inproceedings{Höller_Bercher_2021,
title = {Landmark Generation in HTN Planning},
author = {Daniel H{\"o}ller and Pascal Bercher},
url = {https://ojs.aaai.org/index.php/AAAI/article/view/17405},
doi = {https://doi.org/10.1609/aaai.v35i13.17405},
year = {2021},
date = {2021},
booktitle = {Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI)},
publisher = {AAAI Press},
abstract = {Landmarks (LMs) are state features that need to be made true or tasks that need to be contained in every solution of a planning problem. They are a valuable source of information in planning and can be exploited in various ways. LMs have been used both in classical and hierarchical planning, but while there is much work in classical planning, the techniques in hierarchical planning are less evolved. We introduce a novel LM generation method for Hierarchical Task Network (HTN) planning and show that it is sound and incomplete. We show that every complete approach is as hard as the co-class of the underlying HTN problem, i.e. coNP-hard for our setting (while our approach is in P). On a widely used benchmark set, our approach finds more than twice the number of landmarks than the approach from the literature. Though our focus is on LM generation, we show that the newly discovered landmarks bear information beneficial for solvers.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

The International Planning Competition (IPC) in 2020 wasthe first one for a long time to host tracks on Hierarchical Task Network (HTN) planning. HYPERTENSION, the winner of the tack on totally-ordered problems, comes with an interesting technique: it stores parts of the decomposition path in the state to mark expanded tasks and forces its depth first search to leave recursive structures in the hierarchy. This can be seen as a form of loop detection (LD) – a technique that is not very common in HTN planning. This might be due to the spirit of encoding enough advice in the model to find plans (so that loop detection is simply not necessary), or because it becomes a computationally hard task in the general (i.e. partially-ordered) setting. We integrated several approximate and exact techniques for LD into the progression search of the HTN planner PANDA. We test our techniques on the benchmark set of the IPC 2020. Both in the partial ordered and total ordered track, PANDA with LD performs better than the respective winner of the competition.

• https://ojs.aaai.org/index.php/ICAPS/article/view/15959

@inproceedings{hoeller-behnke-21-LD,
title = {Loop Detection in the PANDA Planning System},
author = {Daniel H{\"o}ller and Gregor Behnke},
url = {https://ojs.aaai.org/index.php/ICAPS/article/view/15959},
year = {2021},
date = {2021-07-21},
booktitle = {Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS)},
pages = {168-173},
publisher = {AAAI Press},
abstract = {The International Planning Competition (IPC) in 2020 wasthe first one for a long time to host tracks on Hierarchical Task Network (HTN) planning. HYPERTENSION, the winner of the tack on totally-ordered problems, comes with an interesting technique: it stores parts of the decomposition path in the state to mark expanded tasks and forces its depth first search to leave recursive structures in the hierarchy. This can be seen as a form of loop detection (LD) – a technique that is not very common in HTN planning. This might be due to the spirit of encoding enough advice in the model to find plans (so that loop detection is simply not necessary), or because it becomes a computationally hard task in the general (i.e. partially-ordered) setting. We integrated several approximate and exact techniques for LD into the progression search of the HTN planner PANDA. We test our techniques on the benchmark set of the IPC 2020. Both in the partial ordered and total ordered track, PANDA with LD performs better than the respective winner of the competition.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

There have been several approaches to use techniques from classical planning in HTN planning. While a direct translation is in general not possible due to the different expressiveness, there have been translations of bounded HTN problems and approaches to use classical heuristics in HTN search procedures. In this paper, we introduce a different approach. We exploit methods from the field of Computational Linguistics introduced to approximate Context-Free Languages by Finite Automata. We use them to approximate the decomposition structure of Totally Ordered (TO) HTN planning problems by classical problems. The resulting problem can then be solved using standard classical planning systems. A subset of TOHTN problems can be translated exactly, i.e., without changing the set of solutions. For problems where an approximation is necessary, we use an overapproximation, i.e., the set of solutions to the classical problem is a superset of that of the HTN problem. We then use plan verification to check whether a solution is valid and thus obtain a sound and complete overall approach. The resulting system outperforms the state of the art on the IPC 2020 benchmark set in terms of coverage.

• https://ojs.aaai.org/index.php/ICAPS/article/view/15958

@inproceedings{hoeller-21-toad,
title = {Translating Totally Ordered HTN Planning Problems to Classical Planning Problems Using Regular Approximation of Context-Free Languages},
author = {Daniel H{\"o}ller},
url = {https://ojs.aaai.org/index.php/ICAPS/article/view/15958},
year = {2021},
date = {2021},
booktitle = {Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS)},
pages = {159-167},
publisher = {AAAI Press},
abstract = {There have been several approaches to use techniques from classical planning in HTN planning. While a direct translation is in general not possible due to the different expressiveness, there have been translations of bounded HTN problems and approaches to use classical heuristics in HTN search procedures. In this paper, we introduce a different approach. We exploit methods from the field of Computational Linguistics introduced to approximate Context-Free Languages by Finite Automata. We use them to approximate the decomposition structure of Totally Ordered (TO) HTN planning problems by classical problems. The resulting problem can then be solved using standard classical planning systems. A subset of TOHTN problems can be translated exactly, i.e., without changing the set of solutions. For problems where an approximation is necessary, we use an overapproximation, i.e., the set of solutions to the classical problem is a superset of that of the HTN problem. We then use plan verification to check whether a solution is valid and thus obtain a sound and complete overall approach. The resulting system outperforms the state of the art on the IPC 2020 benchmark set in terms of coverage.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

Abstract: Polynomial-time heuristic functions for planning are commonplace since 20 years. But polynomial-time in which input? Almost all existing approaches are based on a grounded task representation, not on the actual PDDL input which is exponentially smaller. This limits practical applicability to cases where the grounded representation is „small enough“. Previous attempts to tackle this problem for the delete relaxation leveraged symmetries to reduce the blow-up. Here we take a more radical approach, applying an additional relaxation to obtain a heuristic function that runs in time polynomial in the size of the PDDL input. Our relaxation splits the predicates into smaller predicates of fixed arity K. We show that computing a relaxed plan is still NP-hard (in PDDL input size) for K>=2, but is polynomial-time for K=1. We implement a heuristic function for K=1 and show that it can improve the state of the art on benchmarks whose grounded representation is large.

• https://www.ijcai.org/proceedings/2021/567

@inproceedings{lauer-21,
title = {Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning},
author = {Pascal Lauer and {\'A}lvaro Torralba and Daniel Fišer and Daniel H{\"o}ller and Julia Wichlacz and J{\"o}rg Hoffmann},
url = {https://www.ijcai.org/proceedings/2021/567},
year = {2021},
date = {2021},
booktitle = {Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI)},
pages = {4119-4126},
publisher = {IJCAI organization},
abstract = {Abstract: Polynomial-time heuristic functions for planning are commonplace since 20 years. But polynomial-time in which input? Almost all existing approaches are based on a grounded task representation, not on the actual PDDL input which is exponentially smaller. This limits practical applicability to cases where the grounded representation is "small enough". Previous attempts to tackle this problem for the delete relaxation leveraged symmetries to reduce the blow-up. Here we take a more radical approach, applying an additional relaxation to obtain a heuristic function that runs in time polynomial in the size of the PDDL input. Our relaxation splits the predicates into smaller predicates of fixed arity K. We show that computing a relaxed plan is still NP-hard (in PDDL input size) for K>=2, but is polynomial-time for K=1. We implement a heuristic function for K=1 and show that it can improve the state of the art on benchmarks whose grounded representation is large.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

Planning problems are usually modeled using lifted representations, they specify predicates and action schemas using variables over a finite universe of objects. However, current planning systems like Fast Downward need a grounded (propositional) input model. The process of grounding might result in an exponential blowup of the model size. This limits the application of grounded planning systems in practical applications. Recent work introduced an efficient planning system for lifted heuristic search, but the work on lifted heuristics is still limited. In this extended abstract, we introduce a novel lifted heuristic based on landmarks, which we extract from the lifted problem representation. Preliminary results on a benchmark set specialized to lifted planning show that there are domains where our approach finds enough landmarks to guide the search more effective than the heuristics available.

• https://ojs.aaai.org/index.php/SOCS/article/view/18597

@inproceedings{wichlacz-21,
title = {Landmark Heuristics for Lifted Planning – Extended Abstract},
author = {Julia Wichlacz and Daniel H{\"o}ller and J{\"o}rg Hoffmann},
url = {https://ojs.aaai.org/index.php/SOCS/article/view/18597},
year = {2021},
date = {2021},
booktitle = {Proceedings of the 13th International Symposium on Combinatorial Search (SoCS)},
pages = {242-244},
publisher = {AAAI Press},
abstract = {Planning problems are usually modeled using lifted representations, they specify predicates and action schemas using variables over a finite universe of objects. However, current planning systems like Fast Downward need a grounded (propositional) input model. The process of grounding might result in an exponential blowup of the model size. This limits the application of grounded planning systems in practical applications. Recent work introduced an efficient planning system for lifted heuristic search, but the work on lifted heuristics is still limited. In this extended abstract, we introduce a novel lifted heuristic based on landmarks, which we extract from the lifted problem representation. Preliminary results on a benchmark set specialized to lifted planning show that there are domains where our approach finds enough landmarks to guide the search more effective than the heuristics available.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

Neural networks (NN) have been shown to be powerful state-value predictors in several complex games. Can similar successes be achieved in classical planning? Towards a systematic exploration of that question, we contribute a study of hyperparameter space in the most canonical setup: input = state, feed-forward NN, supervised learning, generalization only over initial state. We investigate a broad range of hyperparameters pertaining to NN design and training. We evaluate these techniques through their use as heuristic functions in Fast Downward. The results on IPC benchmarks show that highly competitive heuristics can be learned, yielding substantially smaller search spaces than standard techniques on some domains. But the heuristic functions are costly to evaluate, and the range of domains where useful heuristics are learned is limited. Our study provides the basis for further research improving on current weaknesses.

• https://ecai2020.eu/papers/433_paper.pdf

@inproceedings{Ferber2020network,
title = {Neural network heuristics for classical planning: A study of hyperparameter space},
author = {Patrick Ferber and J{\"o}rg Hoffmann and Malte Helmert},
url = {https://ecai2020.eu/papers/433_paper.pdf},
year = {2020},
date = {2020},
booktitle = {24th European Conference on Artificial Intelligence (ECAI’20)},
abstract = {Neural networks (NN) have been shown to be powerful state-value predictors in several complex games. Can similar successes be achieved in classical planning? Towards a systematic exploration of that question, we contribute a study of hyperparameter space in the most canonical setup: input = state, feed-forward NN, supervised learning, generalization only over initial state. We investigate a broad range of hyperparameters pertaining to NN design and training. We evaluate these techniques through their use as heuristic functions in Fast Downward. The results on IPC benchmarks show that highly competitive heuristics can be learned, yielding substantially smaller search spaces than standard techniques on some domains. But the heuristic functions are costly to evaluate, and the range of domains where useful heuristics are learned is limited. Our study provides the basis for further research improving on current weaknesses.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

Search methods are useful in hierarchical task network (HTN) planning to make performance less dependent on the domain knowledge provided, and to minimize plan costs. Here we investigate Monte-Carlo tree search (MCTS) as a new algorithmic alternative in HTN planning. We implement combinations of MCTS with heuristic search in Panda. We furthermore investigate MCTS in JSHOP, to address lifted (non-grounded) planning, leveraging the fact that, in contrast to other search methods, MCTS does not require a grounded task representation. Our new methods yield coverage performance on par with the state of the art, but in addition can effectively minimize plan cost over time.

• Wichlacz-SoCS2020     (0.55MB)
• https://ojs.aaai.org/index.php/SOCS/article/view/18538

@inproceedings{Wichlacz20MCTSSOCS,
title = {Applying Monte-Carlo Tree Search in HTN Planning},
author = {Julia Wichlacz and Daniel H{\"o}ller and {\'A}lvaro Torralba and J{\"o}rg Hoffmann},
url = {https://ojs.aaai.org/index.php/SOCS/article/view/18538},
year = {2020},
date = {2020},
booktitle = {Proceedings of the 13th International Symposium on Combinatorial Search (SoCS)},
pages = {82-90},
publisher = {AAAI Press},
address = {Vienna, Austria},
abstract = {Search methods are useful in hierarchical task network (HTN) planning to make performance less dependent on the domain knowledge provided, and to minimize plan costs. Here we investigate Monte-Carlo tree search (MCTS) as a new algorithmic alternative in HTN planning. We implement combinations of MCTS with heuristic search in Panda. We furthermore investigate MCTS in JSHOP, to address lifted (non-grounded) planning, leveraging the fact that, in contrast to other search methods, MCTS does not require a grounded task representation. Our new methods yield coverage performance on par with the state of the art, but in addition can effectively minimize plan cost over time.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

In HTN planning, the hierarchy has a wide impact on solutions. First, there is (usually) no state-based goal given, the objective is given via the hierarchy. Second, it enforces actions to be in a plan. Third, planners are not allowed to add actions apart from those introduced via decomposition, i.e. via the hierarchy. However, no heuristic considers the interplay of hierarchy and actions in the plan exactly (without relaxation) because this makes heuristic calculation NP-hard even under delete relaxation. We introduce the problem class of delete- and ordering-free HTN planning as basis for novel HTN heuristics and show that its plan existence problem is still NP-complete. We then introduce heuristics based on the new class using an integer programming model to solve it.

• Höller-IJCAI-20     (0.3MB)
• https://www.ijcai.org/proceedings/2020/564
• https://doi.org/10.24963/ijcai.2020/564

@inproceedings{Hoeller2020IJCAI,
title = {Delete- and Ordering-Relaxation Heuristics for HTN Planning},
author = {Daniel H{\"o}ller and Pascal Bercher and Gregor Behnke},
url = {https://www.ijcai.org/proceedings/2020/564},
doi = {https://doi.org/10.24963/ijcai.2020/564},
year = {2020},
date = {2020},
booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI)},
pages = {4076-4083},
publisher = {IJCAI organization},
address = {Yokohama, Japan},
abstract = {In HTN planning, the hierarchy has a wide impact on solutions. First, there is (usually) no state-based goal given, the objective is given via the hierarchy. Second, it enforces actions to be in a plan. Third, planners are not allowed to add actions apart from those introduced via decomposition, i.e. via the hierarchy. However, no heuristic considers the interplay of hierarchy and actions in the plan exactly (without relaxation) because this makes heuristic calculation NP-hard even under delete relaxation. We introduce the problem class of delete- and ordering-free HTN planning as basis for novel HTN heuristics and show that its plan existence problem is still NP-complete. We then introduce heuristics based on the new class using an integer programming model to solve it.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

When generating technical instructions, it is often convenient to describe complex objects in the world at different levels of abstraction. A novice user might need an object explained piece by piece, while for an expert, talking about the complex object (e.g. a wall or railing) directly may be more succinct and efficient. We show how to generate building instructions at different levels of abstraction in Minecraft. We introduce the use of hierarchical planning to this end, a method from AI planning which can capture the structure of complex objects neatly. A crowdsourcing evaluation shows that the choice of abstraction level matters to users, and that an abstraction strategy which balances low-level and high-level object descriptions compares favorably to ones which don’t.

• 2020.coling-main.252     (0.77MB)
• https://aclanthology.org/2020.coling-main.252/
• https://doi.org/10.18653/v1/2020.coling-main.252

@inproceedings{kohn-etal-2020-generating,
title = {Generating Instructions at Different Levels of Abstraction},
author = {Arne K{\"o}hn and Julia Wichlacz and {\'A}lvaro Torralba and Daniel H{\"o}ller and J{\"o}rg Hoffmann and Alexander Koller},
url = {https://aclanthology.org/2020.coling-main.252/},
doi = {https://doi.org/10.18653/v1/2020.coling-main.252},
year = {2020},
date = {2020},
booktitle = {Proceedings of the 28th International Conference on Computational Linguistics},
pages = {2802-2813},
publisher = {International Committee on Computational Linguistics},
address = {Barcelona, Spain (Online)},
abstract = {When generating technical instructions, it is often convenient to describe complex objects in the world at different levels of abstraction. A novice user might need an object explained piece by piece, while for an expert, talking about the complex object (e.g. a wall or railing) directly may be more succinct and efficient. We show how to generate building instructions at different levels of abstraction in Minecraft. We introduce the use of hierarchical planning to this end, a method from AI planning which can capture the structure of complex objects neatly. A crowdsourcing evaluation shows that the choice of abstraction level matters to users, and that an abstraction strategy which balances low-level and high-level object descriptions compares favorably to ones which don't.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

We present a comprehensive platform to run human-computer experiments where an agent instructs a human in Minecraft, a 3D blocksworld environment. This platform enables comparisons between different agents by matching users to agents. It performs extensive logging and takes care of all boilerplate, allowing to easily incorporate new agents to evaluate them. Our environment is prepared to evaluate any kind of instruction giving system, recording the interaction and all actions of the user. We provide example architects, a Wizard-of-Oz architect and set-up scripts to automatically download, build and start the platform.

• 2020.sigdial-1.7     (0.64MB)
• https://www.aclweb.org/anthology/2020.sigdial-1.7

@inproceedings{Hoeller2020IJCAIb,
title = {MC-Saar-Instruct: a Platform for Minecraft Instruction Giving Agents},
author = {Arne K{\"o}hn and Julia Wichlacz and Christine Sch{\"a}fer and {\'A}lvaro Torralba and J{\"o}rg Hoffmann and Alexander Koller},
url = {https://www.aclweb.org/anthology/2020.sigdial-1.7},
year = {2020},
date = {2020},
booktitle = {Proceedings of the 21th Annual Meeting of the Special Interest Group on Discourse and Dialogue},
pages = {53-56},
publisher = {Association for Computational Linguistics},
address = {1st virtual meeting},
abstract = {We present a comprehensive platform to run human-computer experiments where an agent instructs a human in Minecraft, a 3D blocksworld environment. This platform enables comparisons between different agents by matching users to agents. It performs extensive logging and takes care of all boilerplate, allowing to easily incorporate new agents to evaluate them. Our environment is prepared to evaluate any kind of instruction giving system, recording the interaction and all actions of the user. We provide example architects, a Wizard-of-Oz architect and set-up scripts to automatically download, build and start the platform.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

To make planning feasible, planning models abstract from many details of the modeled system. When executing plans in the actual system, the model might be inaccurate in a critical point, and plan execution may fail. There are two options to handle this case: the previous solution can be modified to address the failure (plan repair), or the planning process can be re-started from the new situation (re-planning). In HTN planning, discarding the plan and generating a new one from the novel situation is not easily possible, because the HTN solution criteria make it necessary to take already executed actions into account. Therefore all approaches to repair plans in the literature are based on specialized algorithms. In this paper, we discuss the problem in detail and introduce a novel approach that makes it possible to use unchanged, off-the-shelf HTN planning systems to repair broken HTN plans. That way, no specialized solvers are needed.

• 2020-Hoeller-KI     (0.36MB)
• https://link.springer.com/chapter/10.1007/978-3-030-58285-2_7

@inproceedings{Hoeller2020KI,
title = {HTN Plan Repair via Model Transformation},
author = {Daniel H{\"o}ller and Pascal Bercher and Gregor Behnke and Susanne Biundo},
url = {https://link.springer.com/chapter/10.1007/978-3-030-58285-2_7},
year = {2020},
date = {2020},
booktitle = {Proceedings of the 43rd German Conference on Artificial Intelligence (KI)},
pages = {88-101},
publisher = {Springer},
abstract = {To make planning feasible, planning models abstract from many details of the modeled system. When executing plans in the actual system, the model might be inaccurate in a critical point, and plan execution may fail. There are two options to handle this case: the previous solution can be modified to address the failure (plan repair), or the planning process can be re-started from the new situation (re-planning). In HTN planning, discarding the plan and generating a new one from the novel situation is not easily possible, because the HTN solution criteria make it necessary to take already executed actions into account. Therefore all approaches to repair plans in the literature are based on specialized algorithms. In this paper, we discuss the problem in detail and introduce a novel approach that makes it possible to use unchanged, off-the-shelf HTN planning systems to repair broken HTN plans. That way, no specialized solvers are needed.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

Minecraft is a videogame that offers many interesting challenges for AI systems. In this paper, we focus in construction scenarios where an agent must build a complex structure made of individual blocks. As higher-level objects are formed of lower-level objects, the construction can naturally be modelled as a hierarchical task network. We model a house-construction scenario in classical and HTN planning and compare the advantages and disadvantages of both kinds of models.

• whtn19     (0.14MB)
• https://www.semanticscholar.org/paper/Construction-Planning-Models-in-Minecraft-Wichlacz-Torralba/d2ffb1c4b815f1b245f248d436baf9a3c28cc148

@inproceedings{Wichlacz2019,
title = {Construction-Planning Models in Minecraft},
author = {Julia Wichlacz and {\'A}lvaro Torralba and J{\"o}rg Hoffmann},
url = {https://www.semanticscholar.org/paper/Construction-Planning-Models-in-Minecraft-Wichlacz-Torralba/d2ffb1c4b815f1b245f248d436baf9a3c28cc148},
year = {2019},
date = {2019},
booktitle = {Proceedings of the 2nd Workshop on Hierarchical Planning at ICAPS 2019},
pages = {1-5},
abstract = {Minecraft is a videogame that offers many interesting challenges for AI systems. In this paper, we focus in construction scenarios where an agent must build a complex structure made of individual blocks. As higher-level objects are formed of lower-level objects, the construction can naturally be modelled as a hierarchical task network. We model a house-construction scenario in classical and HTN planning and compare the advantages and disadvantages of both kinds of models.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

When generating technical instructions, it is often necessary to describe an object that does not exist yet. For example, an NLG system which explains how to build a house needs to generate sentences like “build a wall of height five to your left” and “now build a wall on the other side.” Generating (indefinite) referring expressions to objects that do not exist yet is fundamentally different from generating the usual definite referring expressions, because the new object must be distinguished from an infinite set of possible alternatives. We formalize this problem and present an algorithm for generating such expressions, in the context of generating building instructions within the Minecraft video game.

• https://www.aclweb.org/anthology/W19-8601
• https://doi.org/10.18653/v1/W19-8601

@inproceedings{Köhn2019,
title = {Talking about what is not there: Generating indefinite referring expressions in Minecraft},
author = {Arne K{\"o}hn and Alexander Koller},
url = {https://www.aclweb.org/anthology/W19-8601},
doi = {https://doi.org/10.18653/v1/W19-8601},
year = {2019},
date = {2019},
booktitle = {Proceedings of the 12th International Conference on Natural Language Generation},
pages = {1-10},
publisher = {Association for Computational Linguistics},
address = {Tokyo, Japan},
abstract = {When generating technical instructions, it is often necessary to describe an object that does not exist yet. For example, an NLG system which explains how to build a house needs to generate sentences like “build a wall of height five to your left” and “now build a wall on the other side.” Generating (indefinite) referring expressions to objects that do not exist yet is fundamentally different from generating the usual definite referring expressions, because the new object must be distinguished from an infinite set of possible alternatives. We formalize this problem and present an algorithm for generating such expressions, in the context of generating building instructions within the Minecraft video game.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard

We present a model which predicts how individual users of a dialog system understand and produce utterances based on user groups. In contrast to previous work, these user groups are not specified beforehand, but learned in training. We evaluate on two referring expression (RE) generation tasks; our experiments show that our model can identify user groups and learn how to most effectively talk to them, and can dynamically assign unseen users to the correct groups as they interact with the system.

• W18-5018     (1.04MB)
• https://arxiv.org/abs/1806.05947

@inproceedings{Engonopoulos2018discovering,
title = {Discovering user groups for natural language generation},
author = {Nikos Engonopoulos and Christoph Teichmann and Alexander Koller},
url = {https://arxiv.org/abs/1806.05947},
year = {2018},
date = {2018},
booktitle = {Proceedings of the 19th Annual SIGdial Meeting on Discourse and Dialogue},
abstract = {We present a model which predicts how individual users of a dialog system understand and produce utterances based on user groups. In contrast to previous work, these user groups are not specified beforehand, but learned in training. We evaluate on two referring expression (RE) generation tasks; our experiments show that our model can identify user groups and learn how to most effectively talk to them, and can dynamically assign unseen users to the correct groups as they interact with the system.},
pubstate = {published},
type = {inproceedings}
}

Copy BibTeX to Clipboard