Creating a PDDL Domain and Problem - Game Kami

Question

I'm currently trying my luck on creating a Plan for the Game Kami. Therefore I need to create a Domain and the Problem in the PDDL language.

Rules of Kami:

The rules are simple. You can color one tile and all neighboring tiles with the same color as you inted. The call is recusive so the neighbours of the neighboring tiles also will get the same color.

Goal:

All tiles should have the same color by using the recursice function described above.

I already got stuck at a 2x2 world of Kami, here you can see my...

... Domain:

(define (domain kami-dom)
    (:requirements :strips :typing :disjunctive-preconditions :negative-preconditions :conditional-effects)

    (:types c - tile
            brown red green - color
    )

    (:predicates
        (color_value ?t - tile ?c - color)
        (is_neighbour ?t ?sec_t - tile)
    )

    (:action color_tile
        :parameters (?t - tile ?old_c ?new_c - color)
        :precondition (and (not (color_value ?t ?new_c)) (color_value ?t ?old_c))
        :effect (and
            (forall (?acc - tile) 
                (when (and (is_neighbour ?t ?acc) (color_value ?acc ?old_c)) 
                    (and (color_value ?acc ?new_c) (not (color_value ?acc ?old_c)))
                )
            )
            (color_value ?t ?new_c)
            (not (color_value ?t ?old_c))
        )
    )
)

... and my Problem.pddl:

(define (problem kami-prob-x-1)
   (:domain kami-dom)

   (:objects
      tile11 tile12 tile21 tile22 - tile
      red green brown - color)

   (:init
      (color_value tile11 red)
      (color_value tile12 red)
      (color_value tile21 red)
      (color_value tile22 brown)

      (is_neighbour tile11 tile12)
      (is_neighbour tile11 tile21)

      (is_neighbour tile12 tile11)
      (is_neighbour tile12 tile22)

      (is_neighbour tile21 tile11)
      (is_neighbour tile21 tile22)
      
      (is_neighbour tile22 tile12)
      (is_neighbour tile22 tile21)
   )
   
   (:goal (or   (and (color_value tile11 red) (color_value tile12 red) (color_value tile21 red) (color_value tile22 red))
                (and (color_value tile11 green) (color_value tile12 green) (color_value tile21 green) (color_value tile22 green))
                (and (color_value tile11 brown) (color_value tile12 brown) (color_value tile21 brown) (color_value tile22 brown)))))

And I can't get a successful plan, even when it is only apllying the function color_tile once.

Answer 1

Concerning your question how to make this recursive. I guess what you want is to have your one action that colours a file that was previously of colour A in colour B to also colour all tiles in the "region" of colour A in colour B. This is commonly called a floodfill. The problem is that PDDL effects do not really support such a kind of recursion in their base version. Instead you can encode the recursion using multiple actions.

What you can do, is to split the floodfill into three steps: starting it, propagation, ending it. For each of the steps you can create a separate action. Additional predicates can be used to keep track of what color you are currently floodfilling and which tiles you have filled. I've modified your domain and problem to do this (see below).

When you perform a turn, you execute the start_color action (color_tile is not applicable). It colors the one tile and sets (a) the current color to the old one the tile had and (b) marks this tile as currently colored. After that this colouring can be propagated using the color_tile action. The coloring is ended with the done_color action. Afterwards, another start_color action can be executed. Using FastDownward (and blind A* search) you get the following optimal plan:

start_color tile25 brown green (1)
color_tile tile25 tile22 brown green (1)
color_tile tile22 tile23 brown green (1)
color_tile tile22 tile24 brown green (1)
done_color  (1)
start_color tile11 red green (1)
color_tile tile11 tile12 red green (1)
color_tile tile11 tile21 red green (1)
done_color  (1)

Note: this modelling might not perfectly what you need. The issue is that you can color adjacent tiles, but you don't have to. You could encode this (in the end done_color), but I guess it will be quite tedious.

Domain:

(define (domain kami-dom)
(:requirements :strips :typing :disjunctive-preconditions :negative-preconditions :conditional-effects)

(:types tile color)

(:predicates
    (color_value ?t - tile ?c - color)
    (currently_colored ?t - tile)
    (current_color ?c - color)
    (is_neighbour ?t ?sec_t - tile)
)

 
(:action start_color
    :parameters (?t - tile ?old_c ?new_c - color)
    :precondition (and 
        (forall (?ot - tile) (not (currently_colored ?ot)))
        (not (color_value ?t ?new_c)) (color_value ?t ?old_c)
    )
    :effect (and
        (color_value ?t ?new_c)
        (not (color_value ?t ?old_c))
        (currently_colored ?t)
        (current_color ?old_c)
    )
)


(:action color_tile
    :parameters (?old_t ?new_t - tile ?old_c ?new_c - color)
    :precondition (and (not (color_value ?new_t ?new_c)) (color_value ?new_t ?old_c) (color_value ?old_t ?new_c) (currently_colored ?old_t) (current_color ?old_c))
    :effect (and
        (color_value ?new_t ?new_c)
        (not (color_value ?new_t ?old_c))
        (currently_colored ?new_t)
    )
)


(:action done_color
    :parameters ()
    :effect (and
        (forall (?t - tile) (not (currently_colored ?t)))
        (forall (?c - color) (not (current_color ?c)))
    )
)
)

Problem:

(define (problem kami-prob-x-1)
(:domain kami-dom)

(:objects
   tile11 tile12 tile21 tile22 tile23 tile24 tile25 - tile
  red green brown - color)

(:init
  (color_value tile11 red)
  (color_value tile12 red)
  (color_value tile21 red)
  (color_value tile22 brown)
  (color_value tile23 brown)
  (color_value tile24 brown)
  (color_value tile25 brown)

  (is_neighbour tile11 tile12)
  (is_neighbour tile11 tile21)

  (is_neighbour tile12 tile11)
  (is_neighbour tile12 tile22)

  (is_neighbour tile21 tile11)
  (is_neighbour tile21 tile22)
  
  (is_neighbour tile22 tile12)
  (is_neighbour tile22 tile21)
  
  (is_neighbour tile22 tile23)
  (is_neighbour tile23 tile22)

  (is_neighbour tile23 tile24)
  (is_neighbour tile24 tile23)

  (is_neighbour tile24 tile25)
  (is_neighbour tile25 tile24)
)

(:goal (and (color_value tile11 green) (color_value tile12 green) (color_value tile21 green) (color_value tile22 green) (color_value tile23 green) (color_value tile24 green) (color_value tile25 green)
            (forall (?t - tile) (not (currently_colored ?t)))
            )
 )
 )

Answer 2

The problem is in the :types description in the domain file. You should replace it by something like:

(:types tile color)

After doing that, if you run some planner, it will return a valid plan. For example, I used Fast Downward (http://www.fast-downward.org/) and got the following output (I removed some irrelevant parts):

color_tile tile11 red brown (1)
[t=0.00733501s, 9896 KB] Plan length: 1 step(s).
[t=0.00733501s, 9896 KB] Plan cost: 1
[t=0.00733501s, 9896 KB] Expanded 2 state(s).

So it does find a plan with a single action that consists of painting tile11.