Solución al problema de las torres de Hanoi usando PDDL

Las torres de hanoi (Explicacion del juego), es un juego-problema clásico muy conocido en las ciencias de la computación dada su complejidad. Una de las ramas en las que cobra interés dicho problema es la planificación en inteligencia artificial dada la complejidad de este problema, palabras más palabras menos la planificación en inteligencia artificial es “El proceso de búsqueda y articulación de una secuencia de acciones que permitan alcanzar un objetivo” (vea más aquí). En este pequeño post pretendo ofrecer una representación de dicho problema en un lenguaje de planificación llamado PDDL (Planning Domain Definition Language) y como esta representación nos ayuda a obtener soluciones a dicho problema usando esta representación en el planificador LPG.

Las Reglas del Juego

Un disco de mayor tamaño no puede ir encima de un disco de menor tamaño. Los discos deben ser apilados de mayor a menos, comenzando desde la base de la torre. Los discos se deben pasar de la torre uno (1) a la torre tres (3). Este juego puede ser jugado en aquí.

Planteamiento del Problema

Una visión general del juego se puede ver de la siguiente manera: planning-1

Definición de Objects

¿Cuáles son los objetos que usaremos en el ejercicio? Tres discos y Tres torres, es decir: disco1, disco2, disco3, torre1, torre2, torre3 Se tendrá un brazo mecánico el cual manipulara los discos.

Estado inicial

El estado inicial de donde parte el problema luce de la siguiente manera: planning-2 Y dicho esto es hora de empezar a definir en lenguaje PDDL cada uno de los elementos que compondrán nuestro problema: (Problema en PDDL quiere decir la especificación de como esta el mundo antes de empezar estado inicial, y como queremos que quede luego de ejecutar el plan es decir estado final). Empezamos con la definición de nuestro problema: Se define la propiedad del objeto, es decir, el objeto “disco1”, se especifica que es un Disco, esto mismo se hace con los demás objetos planning-3 Se debe definir que hay discos de mayor tamaño que otros, con el fin de cumplir una de las reglas de juego. planning-4 Se establece el orden de los discos acorde a su tamaño planning-5 Se define que el disco de la parte superior quedo libre y que el brazo mecánico esta libre. planning-6 Se establece que las torres dos y tres están vacías. planning-7 Así nuestro estado inicial completo quedaría definido así:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
(:domain torres)
(:objects disco1 disco2 disco3 torre1 torre2 torre3)
(:init
(esdisco disco1)
(esdisco disco2)
(esdisco disco3)
(estorre torre1)
(estorre torre2)
(estorre torre3)
(mayor disco3 disco2)
(mayor disco3 disco1)
(mayor disco2 disco1)
(torrevacia torre2)
(torrevacia torre3)
(entorre disco3 torre1)
(encima disco2 disco3)
(encima disco1 disco2)
(libre disco1)
(brazolibre)
)

Es tiempo de definir nuestro objetivo o estado final, una representación gráfica de ese se muestra a continuación: planning-8 Se define el estado de los discos y en la torre que va a quedar, además definir que el disco superior queda libre y que el brazo queda libre.

1
2
3
4
5
6
7
(:goal (and
(entorre disco3 torre3)
(encima disco2 disco3)
(encima disco1 disco2)
(libre disco1)
(brazolibre)
)

Una vez representado nuestro estado inicial y estado final, esto es guardado en un archivo .pddl usualmente llamado problem.pddl (Porque usualmente esto es lo que se quiere resolver). Ahora procederemos a hablar de nuestro dominio o representacion de las acciones que componen el mundo del problema de las torres de hanoi:

Planteamiento del dominio Definición de los predicados que serán usados para representar el estado del mundo: Encima: recibe dos variables que sean discos. Entorre: recibe una variable que sea disco y otra que sea torre. Libre: Pone en estado libre la variable que se le asigne. Sujeto: Al usar el brazo mecánico, el objeto recibido queda sujeto. Brazolibre: El brazo mecánico queda en estado libre. Mayor: Define que la primera variable es mayor que la segunda variable. Estorre: Define que la variable que recibe es una torre. Esdisco: Define que la variable que recibe es un disco. Torrevacia: Define que la torre queda vacía.

1
2
3
4
5
6
7
8
9
10
11
(:predicates 
(encima ?d1 ?d2)
(entorre ?d ?t)
(libre ?d)
(sujeto ?d)
(brazolibre)
(mayor ?d1 ?d2)
(estorre ?t)
(esdisco ?d)
(torrevacia ?t)
)

Definición de las acciones que cambiaran el estado del mundo:

Desapilar

Parámetros:

Recibe dos variables tipo disco.

Precondiciones:

Validar que las dos variables que se reciben si sean discos.

La segunda variable debe ser mayor a la primera variable.

La primera variable debe estar encima de la segunda variable.

La primera Variable debe estar libre.

El brazo mecánico debe estar libre.

Efecto:

La primera variable pasa a tener estado sujeto.

La primera variable deja de estar encima de la segunda variable.

La primera Variable no está libre.

El brazo mecánico no está libre.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(:action desapilar
:parameters (?d1 ?d2)
:precondition (and (esdisco ?d1)
(esdisco ?d2)
(mayor ?d2 ?d1)
(encima ?d1 ?d2)
(libre ?d1)
(brazolibre)
)
:effect (and (sujeto ?d1)
(not (encima ?d1 ?d2))
(not (brazolibre))
(not (libre ?d1))
(libre ?d2)
)
)

Coger

Parámetros:

Recibe una variable tipo disco y una variable tipo torre.

Precondiciones:

La primera variable debe ser tipo disco

La segunda variable debe ser tipo Torre.

La primera variable debe estar libre.

La primera variable debe estar en la torre definida en la segunda

El brazo mecánico debe estar libre.

La torre no puede estar vacía.

Efecto:

La primera variable pasa a tener estado sujeto.

La primera variable deja de estar en la torre de la segunda variable.

La primera Variable no está libre.

El brazo mecánico no está libre.

La torre de la segunda variable pasa a estar vacía.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(:action coger
:parameters (?d1 ?t1)
:precondition (and (esdisco ?d1)
(estorre ?t1)
(libre ?d1)
(entorre ?d1 ?t1)
(brazolibre)
(not (torrevacia ?t1))
)
:effect (and (sujeto ?d1)
(not (entorre ?d1 ?t1))
(not (brazolibre))
(not (libre ?d1))
(torrevacia ?t1)
)
)

Apilar

Parámetros:

Recibe dos variables tipo disco.

Precondiciones:

Validar que las dos variables que se reciben si sean discos.

La segunda variable debe ser mayor a la primera variable.

La primera variable debe estar con estado

La segunda Variable debe estar libre.

La primera variable no debe estar encima de la segunda variable.

El brazo mecánico no está libre.

La primera Variable no está libre.

Efecto:

La primera Variable pasa a estar libre.

La primera variable pasa a estar encima de la segunda variable.

El brazo mecánico pasa a estar libre.

La primera variable pasa a tener estado no sujeto.

La segunda Variable no está libre.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
(:action apilar
:parameters (?d1 ?d2)
:precondition (and (esdisco ?d1)
(esdisco ?d2)
(mayor ?d2 ?d1)
(sujeto ?d1)
(libre ?d2)
(not (encima ?d1 ?d2))
(not (brazolibre))
(not (libre ?d1))
)
:effect (and (libre ?d1)
(encima ?d1 ?d2)
(brazolibre)
(not (sujeto?d1))
(not (libre ?d2))
)
)

Poner

Parámetros:

Recibe una variable tipo disco y una variable tipo torre.

Precondiciones:

La primera variable debe ser tipo disco

La segunda variable debe ser tipo Torre.

La primera variable debe estar en estado sujeto.

La primera variable no debe estar en la torre definida en la segunda variable.

El brazo mecánico no debe estar libre.

La primera variable no debe estar libre.

La torre debe estar vacía.

Efecto:

La primera variable pasa a estar en la torre de la segunda variable.

La primera Variable pasa a estar libre.

El brazo mecánico pasa a estar libre.

La primera variable pasa a tener estado no sujeto.

La torre de la segunda variable pasa a estar ocupada.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
(:action poner
:parameters (?d1 ?t1)
:precondition (and (esdisco ?d1)
(estorre ?t1)
(sujeto ?d1)
(not (entorre ?d1 ?t1))
(not (brazolibre))
(not (libre ?d1))
(torrevacia ?t1)
)
:effect (and (entorre ?d1 ?t1)
(libre ?d1)
(brazolibre)
(not (sujeto?d1))
(not (torrevacia ?t1)))
)

Hecho esto volcamos todo nuestro dominio a un archivo denominado domain.pddl. Ya con nuestros dos archivos domain.pddl y problem.pddl estamos listos para que nuestro planificador nos muestre posibles secuencias de acciones para llegar a la solución de nuestro problema, a continuación presento una de ellas: planning-15 Es posible también realizar algunas variantes para soportar el problema con 4, 8 o N discos solo es cuestión de jugar un poco con el problem.pddl. Para descargar los archivos problem.pddl o domain.pddl haz click sobre sus titulos.

Copyrights © 2018 Sebastian Gomez. All Rights Reserved.

Sobre mí

sebastianMi nombre es Sebastián Gómez, soy ingeniero de sistemas e Informática y Magister en Ingeniería de Sistemas de la Universidad Nacional de Colombia.

Actualmente trabajo en Globant como Web UI Developer con énfasis en aplicaciones híbridas y cross compiladas. Soy el organizador del Google Developers Group de Medellín, así que contactame si quieres dar alguna charla o participar actuamente de esta comunidad.

He participado en una Startup Colombiana llamada SponzorMe al lado de Carlos Rojas y fuí participante de Startup Chile a pesar de no haber continuado con esta startup me apasiona el emprendimiento y me gusta aconsejar y ayudar startups como mentor técnico. También he trabajado en empresas Americanas como StudioHyperset en Estados Unidos y para Measured Medium. Mi interés y mi experiencia es el desarrollo de web y móvil full stack como Front-end con Javascript. Me apasiona desarrollar software, escribir código y enseñar lo que aprendo día a día.

También he trabajado como profesor en diferentes universidades en Medellín Colombia, con tematicas relacionadas con la Inteligencia Artificial, Bases de datos, programación orientada a objetos, minería de datos, desarrollo de software, desarrollo móvil y desarrollo web.

Me encanta escribir código rápido y prototipar de una manera accelerada si quieres ver que hago día a día puedes darle un vistazo a mi codepen:  https://codepen.io/seagomezar/.

Todos los días trato de crear o participar en proyectos, la mayoría open source, así que puede chequear mi GitHub:  https://github.com/seagomezar.

Mi áreas de investigación académica son: Ingeniería de software, Ingeniería de requisitos, procesamiento del lenguaje natural, Ontologías, Bases De Datos,  Machine Learning, Seguimiento de trayectorias y Modelamiento matemático de formaciones.

Estas son algunas de mis publicaciones académicas mas recientes: