1

我被要求为著名的“山羊、狼和卷心菜”场景写一个解决方案。场景如下：

农夫想把这三个人都运过河。但是，如果：

  • 山羊和白菜一个人呆着，山羊会吃白菜
  • 如果狼和山羊一个人呆着，狼会吃掉山羊！

因此，该问题的一种解决方案如下：

  • 把山羊带过河，然后把它扔到另一边
  • 过河回来
  • 拿起卷心菜或狼，把它带到另一边
  • 放下狼，捡起山羊，然后回到另一边
  • 放下山羊，拿起卷心菜，然后回到另一边
  • 拿起山羊，瞧！这三个都被运输了。

但是，我无法将其投影到 PDDL 中。我已经给出了问题定义：

(define 
(problem boat1)
(:domain boat)
; only needs two objects, namely representing
; either banke side of the river, [w]est and [e]ast
(:objects  w e)
(:INIT 
    ; wolf, goat, cabbage, boat are all on 
    ; the west side to start with
    (config w w w w)

    ; represent all valid states
    ; these two are the special case,
    ; representing that wolf and cabbage are
    ; safe together even if the boat is away
    (valid w e w e)
    (valid e w e w)

    ; these are all cases where two entities
    ; are always safe as long as the boat is 
    ; with them. In other words, a single entity
    ; on the other side is also always safe
    ; for west side
    (valid w w w w)
    (valid w w e w)
    (valid w e w w)
    (valid e w w w)
    ; for east side
    (valid e e e e)
    (valid e e w e)
    (valid e w e e)
    (valid w e e e)
    ; these are all valid states that are
    ; ever allowed


)

(:goal (AND 
        ; they all have to move to the east side
        (config e e e e)
    )
)

最后，我们只得到了 1 个谓词，并被告知这可以通过 4 个动作来完成。move_empty，move_goat，move_wolf，move_cabbage。

谓词是：

（配置？狼？山羊？卷心菜？船）（有效？狼？山羊？卷心菜？船）

我试图从 move_empty 开始：

    (:action move_empty
     :parameters (?from ?to)
     :precondition (and (valid ?x ?y ?z ?w) (on_left ?from) (on_right ?to))                      
     :effect (and (valid ?x ?y ?z ?w)))

我不希望得到答案，只希望得到关于如何解决这个问题的帮助和建议，因为我能找到的关于 PDDL 的信息并不多。

4

1 回答 1

2

注意：我不知道pddl语言，这是我通过查看您的代码获得的。

大意

在您的问题中，每个实体都被描述为位于河流的西岸或东岸，并且使用它们在谓词config和valid中的相对位置来识别实体。

每个动作都从一个给定的配置开始，并且必须以另一个配置结束。此外，我们必须要求最终 配置有效。

所以从银行东边到西边的move_empty就这么简单：

  (:action move_empty_ew :parameters (?x ?y ?z)
   :precondition (and (config ?x ?y ?z e) (valid ?x ?y ?z w))
   :effect (and (not (config ?x ?y ?z e)) (config ?x ?y ?z w))
  )

在这里，我们让所有其他实体（狼、山羊和卷心菜）的位置不确定，而我们要求最初船在东岸，让船在离开动物的同时开到西岸无人看管是一个有效的举动。如果满足所有这些条件，那么我们将转到所需的配置。

解决方案

请注意，我改进了操作的名称，以便它们提供更多信息。正在采取的实际行动。

船域.pdfl

(define (domain boat)
  (:requirements :equality)

  (:predicates
    (config ?wolf ?goat ?cabbage ?boat)
    (valid ?wolf ?goat ?cabbage ?boat)
  )

  (:action move_empty_ew :parameters (?x ?y ?z)
   :precondition (and (config ?x ?y ?z e) (valid ?x ?y ?z w))
   :effect (and (not (config ?x ?y ?z e)) (config ?x ?y ?z w))
  )
  (:action move_empty_we :parameters (?x ?y ?z)
   :precondition (and (config ?x ?y ?z w) (valid ?x ?y ?z e))
   :effect (and (not (config ?x ?y ?z w)) (config ?x ?y ?z e))
  )

  (:action move_wolf_ew :parameters (?y ?z)
   :precondition (and (config e ?y ?z e) (valid w ?y ?z w))
   :effect (and (not (config e ?y ?z e)) (config w ?y ?z w))
  )
  (:action move_wolf_we :parameters (?y ?z)
   :precondition (and (config w ?y ?z w) (valid e ?y ?z e))
   :effect (and (not (config w ?y ?z w)) (config e ?y ?z e))
  )

  (:action move_goat_ew :parameters (?x ?z)
   :precondition (and (config ?x e ?z e) (valid ?x w ?z w))
   :effect (and (not (config ?x e ?z e)) (config ?x w ?z w))
  )
  (:action move_goat_we :parameters (?x ?z)
   :precondition (and (config ?x w ?z w) (valid ?x e ?z e))
   :effect (and (not (config ?x w ?z w)) (config ?x e ?z e))
  )

  (:action move_cabbage_ew :parameters (?x ?y)
   :precondition (and (config ?x ?y e e) (valid ?x ?y w w))
   :effect (and (not (config ?x ?y e e)) (config ?x ?y w w))
  )
  (:action move_cabbage_we :parameters (?x ?y)
   :precondition (and (config ?x ?y w w) (valid ?x ?y e e))
   :effect (and (not (config ?x ?y w w)) (config ?x ?y e e))
  )
)

船-prob.pddl

(define (problem boat)
  (:domain boat)
  (:objects w e)

  (:INIT (config w w w w)
    (valid w e w e) (valid e w e w)
    (valid w w w w) (valid w w e w)
    (valid w e w w) (valid e w w w)
    (valid e e e e) (valid e e w e)
    (valid e w e e) (valid w e e e)
  )

  (:goal (config e e e e))
)

我使用快速向下找到最小长度的解决方案：

~$ fast-downward.py --alias seq-opt-bjolp boat-domain.pddl boat-prob.pddl

这实际上是：

move_goat_we w w (1)
move_empty_ew w e w (1)
move_cabbage_we w e (1)
move_goat_ew w e (1)
move_wolf_we w e (1)
move_empty_ew e w e (1)
move_goat_we e e (1)
Plan length: 7 step(s).
Plan cost: 7
于 2016-05-17T17:40:51.317 回答