In this work we face a challenging puzzle video game: A Good Snowman is Hard
to Build. The objective of the game is to build snowmen by moving and stacking
snowballs on a discrete grid. For the sake of player engagement with the game,
it is interesting to avoid that a player finds a much easier solution than the
one the designer expected. Therefore, having tools that are able to certify the
optimality of solutions is crucial.
Although the game can be stated as a planning problem and can be naturally
modelled in PDDL, we show that a direct translation to SAT clearly outperforms
off-the-shelf state-of-the-art planners. As we show, this is mainly due to the
fact that reachability properties can be easily modelled in SAT, allowing for
shorter plans, whereas using axioms to express a reachability derived predicate
in PDDL does not result in any significant reduction of solving time with the
considered planners. We deal with a set of 51 levels, both original and
crafted, solving 43 and with 8 challenging instances still remaining to be
solved.

通过使用 SAT 方法解决难题视频游戏，我们证明了直接将游戏转换为 SAT 显著超过了现有的先进规划器的性能，主要原因是 SAT 能够轻松建模可达性属性，从而获得更短的解决方案。

制作一个优秀的雪人是困难的

A Good Snowman is Hard to Plan

In this paper, we study LTLf synthesis under environment specifications for
arbitrary reachability and safety properties. We consider both kinds of
properties for both agent tasks and environment specifications, providing a
complete landscape of synthesis algorithms. For each case, we devise a specific
algorithm (optimal wrt complexity of the problem) and prove its correctness.
The algorithms combine common building blocks in different ways. While some
cases are already studied in literature others are studied here for the first
time.

本文研究了针对任意可达性和安全性属性的环境规范下的 LTLf 综合，考虑了代理任务和环境规范的两种属性，提供了一系列完整的综合算法。针对每种情况，我们设计了一个特定算法（关于问题复杂性最优），并证明了其正确性。这些算法通过不同的方式组合了常见的构建模块。虽然一些情况已经在文献中得到研究，但其他情况本文首次进行了研究。