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语言,这是我通过查看您的代码获得的。


大意

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

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

所以从银行东边西边的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 回答