2

我在 PDDL 中尝试生成推箱子关卡,发现推箱子中的许多关卡对人类来说似乎很容易,但对 PDDL 规划者来说似乎相当困难(老实说,我也发现了反之亦然的例子)。

所以我想知道是否有一个计划器可以在 i7 16GB 内存等中等硬件上找到这个推箱子级别的解决方案(可在https://sokoban.info/?1_2上播放),即原始推箱子游戏的第二关似乎对人类来说相当容易:

############
#..--#-----###
#..--#-$--$--#
#..--#$####--#
#..----@-##--#
#..--#-#--$-##
######-##$-$-#
--#-$--$-$-$-#
--#----#-----#
--############

此级别编码在以下 PDDL 文件中(如果您认为此演示文稿相当不适合 PDDL 规划人员,请告诉我 - 我不这么认为)。我使用仿真仔细检查了 PDDL 文件,并且可以通过手动创建的计划成功获得目标。

然而,有了计划者,我可以得到我的手(Fast Downward,ArvandHerd,siw-then-bfsf),这需要很长时间(几小时/几天),直到进程因使用太多内存而被终止。

那么你有没有一个计划者可以用合理的资源解决这个难题?!

领域:

(define (domain sokoban)
  (:requirements :strips :negative-preconditions)
  (:predicates (adjwe ?h1 ?h2) (adjsn ?v1 ?v2)
        (sokoban_at ?h ?v) (wall_at ?h ?v) (crate_at ?h ?v)
  )
  (:action move-n
   :parameters (?x1 ?y0 ?y1)
   :precondition (and
        (adjsn ?y0 ?y1)

        (sokoban_at ?x1 ?y0)
        (not (crate_at ?x1 ?y1)) (not (wall_at ?x1 ?y1))
    )
   :effect (and
        (not (sokoban_at ?x1 ?y0))
        (sokoban_at ?x1 ?y1)
    )
  )
  (:action push-n
   :parameters (?x1 ?y0 ?y1 ?y2)
   :precondition (and
        (adjsn ?y0 ?y1) (adjsn ?y1 ?y2)

        (sokoban_at ?x1 ?y0) (crate_at ?x1 ?y1)
        (not (crate_at ?x1 ?y2)) (not (wall_at ?x1 ?y2))
    )
   :effect (and
        (not (sokoban_at ?x1 ?y0)) (not (crate_at ?x1 ?y1))
        (sokoban_at ?x1 ?y1) (crate_at ?x1 ?y2)
    )
  )
  (:action move-s
   :parameters (?x1 ?y0 ?y1)
   :precondition (and
        (adjsn ?y1 ?y0)

        (sokoban_at ?x1 ?y0)
        (not (crate_at ?x1 ?y1)) (not (wall_at ?x1 ?y1))
    )
   :effect (and
        (not (sokoban_at ?x1 ?y0))
        (sokoban_at ?x1 ?y1)
    )
  )
  (:action push-s
   :parameters (?x1 ?y0 ?y1 ?y2)
   :precondition (and
        (adjsn ?y1 ?y0) (adjsn ?y2 ?y1)

        (sokoban_at ?x1 ?y0) (crate_at ?x1 ?y1)
        (not (crate_at ?x1 ?y2)) (not (wall_at ?x1 ?y2))
    )
   :effect (and
        (not (sokoban_at ?x1 ?y0)) (not (crate_at ?x1 ?y1))
        (sokoban_at ?x1 ?y1) (crate_at ?x1 ?y2)
    )
  )
  (:action move-e
   :parameters (?x1 ?x2 ?y1)
   :precondition (and
        (adjwe ?x1 ?x2)

        (sokoban_at ?x1 ?y1)
        (not (crate_at ?x2 ?y1)) (not (wall_at ?x2 ?y1))
    )
   :effect (and
        (not (sokoban_at ?x1 ?y1))
        (sokoban_at ?x2 ?y1)
    )
  )
  (:action push-e
   :parameters (?x1 ?x2 ?x3 ?y1)
   :precondition (and
        (adjwe ?x1 ?x2) (adjwe ?x2 ?x3)

        (sokoban_at ?x1 ?y1) (crate_at ?x2 ?y1)
        (not (crate_at ?x3 ?y1)) (not (wall_at ?x3 ?y1))
    )
   :effect (and
        (not (sokoban_at ?x1 ?y1)) (not (crate_at ?x2 ?y1))
        (sokoban_at ?x2 ?y1) (crate_at ?x3 ?y1)
    )
  )
  (:action move-w
   :parameters (?x1 ?x2 ?y1)
   :precondition (and
        (adjwe ?x2 ?x1)

        (sokoban_at ?x1 ?y1)
        (not (crate_at ?x2 ?y1)) (not (wall_at ?x2 ?y1))
    )
   :effect (and
        (not (sokoban_at ?x1 ?y1))
        (sokoban_at ?x2 ?y1)
    )
  )
  (:action push-w
   :parameters (?x1 ?x2 ?x3 ?y1)
   :precondition (and
        (adjwe ?x2 ?x1) (adjwe ?x3 ?x2)

        (sokoban_at ?x1 ?y1) (crate_at ?x2 ?y1)
        (not (crate_at ?x3 ?y1)) (not (wall_at ?x3 ?y1))
    )
   :effect (and
        (not (sokoban_at ?x1 ?y1)) (not (crate_at ?x2 ?y1))
        (sokoban_at ?x2 ?y1) (crate_at ?x3 ?y1)
    )
  )
)

问题:

(define (problem sokoban02)
    (:domain sokoban)
    (:objects
        h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 h12 h13 h14
        v2 v3 v4 v5 v6 v7 v8 v9 v10 v11
    )
    (:init
        (adjwe h1 h2) (adjwe h2 h3) (adjwe h3 h4) (adjwe h4 h5) (adjwe h5 h6) (adjwe h6 h7) (adjwe h7 h8) (adjwe h8 h9) (adjwe h9 h10) (adjwe h10 h11) (adjwe h11 h12) (adjwe h12 h13) (adjwe h13 h14)
        (adjsn v2 v3) (adjsn v3 v4) (adjsn v4 v5) (adjsn v5 v6) (adjsn v6 v7) (adjsn v7 v8) (adjsn v8 v9) (adjsn v9 v10) (adjsn v10 v11)
        
        (wall_at h1 v11) (wall_at h2 v11) (wall_at h3 v11) (wall_at h4 v11) (wall_at h5 v11) (wall_at h6 v11) (wall_at h7 v11) (wall_at h8 v11) (wall_at h9 v11) (wall_at h10 v11) (wall_at h11 v11) (wall_at h12 v11) (wall_at h1 v10) (wall_at h6 v10) (wall_at h12 v10) (wall_at h13 v10) (wall_at h14 v10) (wall_at h1 v9) (wall_at h6 v9) (wall_at h14 v9) (wall_at h1 v8) (wall_at h6 v8) (wall_at h8 v8) (wall_at h9 v8) (wall_at h10 v8) (wall_at h11 v8) (wall_at h14 v8) (wall_at h1 v7) (wall_at h10 v7) (wall_at h11 v7) (wall_at h14 v7) (wall_at h1 v6) (wall_at h6 v6) (wall_at h8 v6) (wall_at h13 v6) (wall_at h14 v6) (wall_at h1 v5) (wall_at h2 v5) (wall_at h3 v5) (wall_at h4 v5) (wall_at h5 v5) (wall_at h6 v5) (wall_at h8 v5) (wall_at h9 v5) (wall_at h14 v5) (wall_at h3 v4) (wall_at h14 v4) (wall_at h3 v3) (wall_at h8 v3) (wall_at h14 v3) (wall_at h3 v2) (wall_at h4 v2) (wall_at h5 v2) (wall_at h6 v2) (wall_at h7 v2) (wall_at h8 v2) (wall_at h9 v2) (wall_at h10 v2) (wall_at h11 v2) (wall_at h12 v2) (wall_at h13 v2) (wall_at h14 v2)
        (crate_at h8 v9) (crate_at h11 v9) (crate_at h7 v8) (crate_at h11 v6) (crate_at h10 v5) (crate_at h12 v5) (crate_at h5 v4) (crate_at h8 v4) (crate_at h10 v4) (crate_at h12 v4)
        (sokoban_at h8 v7)
    )
    (:goal (and (crate_at h2 v10) (crate_at h3 v10) (crate_at h2 v9) (crate_at h3 v9) (crate_at h2 v8) (crate_at h3 v8) (crate_at h2 v7) (crate_at h3 v7) (crate_at h2 v6) (crate_at h3 v6)))
)
4

1 回答 1

2

尝试使用单个对象对坐标进行编码,(at pos-x-y)而不是(at x y). 它可以提高您正在尝试的规划器的性能。请参阅此IPC 推箱子编码示例。

您还可以尝试推箱子特定的计划器,例如 Festival,最近在 SoCS 上推出的最新迭代:https ://festival-solver.site/

于 2021-11-17T23:51:12.890 回答