proyecto fin de carrera ingenier´ıa de...

Proyecto Fin de CarreraIngenierıa de Telecomunicacion

Desarrollo de una librerıa para el manejo dePOMDPs con Diagramas de Decision Algebraicos

Autor: Paula Garcıa GilDirector: D. Jesus Capitan Fernandez

Ingenierıa de Sistemas y AutomaticaEscuela Tecnica Superior de IngenierıaUniversidad de SevillaSevilla, 2014

Proyecto Fin de CarreraIngenierıa de Telecomunicacion

Desarrollo de una librerıa para el manejo de POMDPs con Diagramas deDecision Algebraicos

Autor:

Paula Garcıa Gil

Director:

D. Jesus Capitan FernandezProfesor Ayudante Doctor

Ingenierıa de Sistemas y AutomaticaEscuela Tecnica Superior de Ingenierıa

Universidad de Sevilla

2014

Agradecimientos

Quiero comenzar agradeciendo a mis companeros de carrera el apoyo y ayuda recibida du-rante estos seis anos, ya que de no ser por ellos no estarıa aquı hoy, realizando este proyecto, enparticular a aquellos que ya no son solo companeros, si no verdaderos amigos.

Por supuesto, tambien a mis amigas de toda la vida, aquellas que siempre estan ahı, aunquecada vez sea mas dificil hacer que estemos todas juntas, sin olvidarme de mis companeras deOporto, personas que mas que amigas se convirtieron en hermanas durante ese ano que tantoaprendimos, tanto academica como personalmente.

Tambien, me gustarıa agradecer la oportunidad de realizar este proyecto a D. Jesus CapitanFernandez, ası como su constante ayuda en el desarrollo del mismo.

Y como lo mejor se deja para el final, quiero agradecer, a mi madre, que ha estado todo estetiempo apoyandome de manera incondicional, a mi padre por sus consejos, a mi hermana quesiempre me ha apoyado, y por supuesto, a Ismael que es quien mas ha aguantado mis desplantesy mis agobios, las horas y horas sin salir de casa por acabar este proyecto y que se ha leıdo yreleıdo este documento hasta que ha estado perfecto.

Paula Garcıa Gil

Sevilla, 2014

i

Resumen

Los Procesos de Decision de Markov (MDPs) son modelos matematicos que permiten modelarla toma de decisiones optimas en situaciones en las que hay algun componente aleatorio.

Los Procesos de Decision de Markov Parcialmente Observables (POMDPs, por sus siglas eningles) son aquellos que modelan sistemas dominados por un MDP, con la diferencia de que elagente no puede observar directamente el estado en el que se encuentra. Este tipo de procesosmodela multitud de problemas de la vida real, y permiten obtener polıticas para tomar decisionesde manera optima.

Este proyecto fin de carrera se centra en la obtencion de una librerıa que proporcione todaslas operaciones necesarias para trabajar con este tipo de procesos. Para ello, se ha partido deuna librerıa ya existente en el lenguaje de programacion Java para crear otra con la mismafuncionalidad en el lenguaje de programacion C++. El objetivo de este documento, no es, enningun caso, la realizacion de un resolvedor de polıticas para POMDPs, si no, unicamente, laobtencion de las funciones necesarias para operar con ellos.

Este documento es, basicamente, una guıa para la utilizacion de esta librerıa, que abarcatanto su estructura interna, como el resumen de la funcionalidad de cada una de sus operaciones,ası como una baterıa de pruebas de funcionamiento, finalizando con la simulacion de un procesocompleto.

El primer capıtulo es una introduccion basica a los procesos de decision de Markov par-cialmente observables, donde se explica en que consisten y algun ejemplo de uso de losmismos.

El segundo capıtulo consiste en una descripcion de los ficheros, clases y metodos quecomponen la solucion proporcionada.

El tercero detalla la relacion de pruebas realizadas ası como sus resultados. En este capıtulose incluye como prueba final una simulacion manual de la evolucion de los estados de unrobot.

El cuarto y ultimo capıtulo muestra las coclusiones que podemos obtener de este trabajo.

iii

Indice general

1. Introduccion 1

1.1. Introduccion a los Procesos de Decision de Markov (MDP) . . . . . . . . . . . . . 1

1.2. Introduccion a los Procesos de Decision de Markov Parcialmente Observables(POMDP) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2. Estructura de la librerıa 7

2.1. Clase DD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2. Clase MySet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3. Clase Config . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.4. Clase DDcollection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5. Clase CacheMap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5.1. Aspectos importantes en el uso de mapas hash . . . . . . . . . . . . . . . 17

2.6. Clase Global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.7. Clase OP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.8. Clase ParseSPUDD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3. Pruebas funcionales y simulacion 39

3.1. Pruebas funcionales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2. Simulacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

4. Conclusiones 51

A. Aspectos tecnicos 55

v

B. Prueba de suma y calculos de tiempo 57

vi

Indice de figuras

1.1. Area de movimiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2. Ejemplo DD funcion de observacion . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1. Ejemplo de DD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.2. Ejemplo de suma de DDs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.3. Ejemplo de maxout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4. Ejemplo de extractConfig . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.5. Calculo de nEdges, nLeaves, nNodes y getNumLeavesDepth . . . . . . . . . . . . 26

3.1. Cuadrıcula de posiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2. Belief inicial sobre el estado para la simulacion. Paso 1/5 . . . . . . . . . . . . . 45

3.3. Belief sobre el estado para la simulacion. Paso 2/5 . . . . . . . . . . . . . . . . . 46




vii

Capıtulo 1Introduccion

1.1. Introduccion a los Procesos de Decision de Markov (MDP)

Los Procesos de Decision de Markov (MDPs) proporcionan un marco matematico para mo-delar la toma de decisiones en situaciones que tienen una parte aleatoria y otra parte que vienedeterminada por la toma de decisiones de algun agente decisor. Los MDPs son utiles para estu-diar una amplia gama de problemas de optimizacion resueltos mediante programacion dinamicay aprendizaje por recompensa. Se utilizan en una amplia gama de disciplinas, incluyendo larobotica, el control automatizado, la economıa y la manufactura.

Siendo mas especıficos, un proceso de decision de Markov es un proceso de control estocasticode tiempo discreto. Por cada intervalo de tiempo, el proceso estara en un estado concreto s, yel agente que toma las decisiones puede elegir cualquier accion a que este disponible para elestado actual. El proceso respondera moviendo el proceso a un estado s’ y dando al decisor larecompensa correspondiente R(s, a).

La probabilidad de que el proceso se mueva de un estado s a otro estado s’ esta influenciadapor la accion elegida. En concreto, viene dada por la funcion de transicion de estado T(s’, a, s).Por lo tanto, el siguiente estado s’ depende tanto del estado actual s como de la accion decididaa. Estas transiciones deben cumplir la propiedad de Markov, carecer de memoria, dependerandel estado s actual y la decision tomada a pero nunca de los anteriores valores de estas variables[1].

Dicho todo esto, el proceso puede ser resumido de la forma siguiente:

Se observa el estado s de una cadena de Markov de tiempo discreto despues de cadatransicion (s = 0, 1, ..., M).

Despues de cada observacion, se selecciona una decision (accion) a de un conjunto de Ndecisiones posibles (a = 0, 1,..., N-1). Algunas de las N decisiones pueden no ser relevantespara algunos estados.

1

2 CAPITULO 1. INTRODUCCION

Si se elige la decision as = d en el estado s, se determinaran cuales seran las probabilidadesde transicion a traves de la distribucion de probabilidad dada por T(s’, a, s) paras’ = 0, 1, ..., M.

Una especificacion de las decisiones para los estados respectivos (a0, a1, ..., aN−1) describeuna polıtica para el proceso de decision markoviano.

El objetivo es encontrar una polıtica optima de acuerdo con algun criterio de coste queconsidere tanto los costes inmediatos como los subsecuentes que resulten de la evolucionfutura del proceso. Un criterio comun es minimizar el coste promedio esperado por launidad de tiempo [2].

Los procesos de decision de Markov son una extension de las cadenas de Markov, la diferenciaes la adicion de acciones, que permiten la eleccion, y de recompensas, dando la motivacion. Portanto, si solo existe una accion para cada estado y todas las recompensas son iguales, un procesode decision de Markov se reduce a una cadena de Markov [3].

1.2. Introduccion a los Procesos de Decision de Markov Parcial-mente Observables (POMDP)

Los procesos de decision de Markov parcialmente observables (POMDPs) son una generaliza-cion de los MDPs. En un MDP se considera observabilidad completa del sistema, por el contrario,un POMDP modela sistemas con observabilidad limitada del estado en el que se encuentra. Enun POMDP, en vez de conocer el estado directamente, el agente mantiene una distribucion deprobabilidad sobre el conjunto de estados S. Esta distribucion de probabilidad sobre el conjuntode estados se conoce como creencia o belief.

Este tipo de procesos valen para modelar un gran variedad de procesos de decision secuencia-les del mundo real. Un proceso de decision secuencial es aquel en el cual un sistema evolucionaen el tiempo y es controlado por un agente. Estas aplicaciones incluyen movimiento de robots,mantenimiento de maquinas, y problemas de decision bajo incertidumbre en general.

Una polıtica para un POMDP viene dada por la lista de acciones para cada creencia posible.La accion optima es aquella que maximiza la recompensa que obtiene el agente decisor sobreun cierto horizonte temporal. La secuencia de las acciones optimas es conocida como la polıticaoptima del agente para interactuar con su entorno.

Resolver este tipo de sistemas conlleva una dificultad computacional muy alta, solo encontrarla polıtica optima que maximice la recompensa para un horizonte finito T ya es muy costoso,por lo que la dificultad de intentar hacerlo para un horizonte infinito puede ser excesiva [4] [5].

A continuacion se detallan las diferentes partes que componen un proceso de decision deMarkov parcialmente observable:

1.2 Introduccion a los Procesos de Decision de Markov Parcialmente Observables(POMDP) 3

Espacio de estadosToda la informacion relevante sobre el entorno es codificada en el estado, el cual no escompletamente observable. Esto significa que este estado no puede ser observado directa-mente, y una distribucion de probabilidad sobre el conjunto de posibles estados debe sermantenida basandonos en las observaciones de los sensores. El estado del sistema en cadaintervalo de tiempo es definido por st ∈ S, donde S es el conjunto finito de los posiblesestados.

Espacio de accionesEl agente puede realizar una accion sobre el entorno en cada intervalo de tiempo. Estasacciones modifican el estado de un modo estocastico. A es el conjunto finito de las posiblesacciones, y at ∈ A es la accion tomada en un intervalo de tiempo t.

Espacio de observacionDado un intervalo de tiempo t, despues de la ejecucion de una accion, un agente puedetomar una medida u observacion zt ∈ Z, donde Z es el conjunto finito de las posiblesobservaciones. Una observacion es informacion sobre el entorno que percibe el agente.

Funcion de transicionCuando un agente ejecuta una accion, el estado puede variar probabilısticamente. Estafuncion de densidad de probabilidad es modelada por la funcion de transicion T : S×A×S → [0, 1], donde T (s′, a, s) = p(st = s′|at−1 = a, st−1 = s), que representa la probabilidadde llegar a un estado s’ desde un estado s ejecutada una accion a.

Funcion de observacionLas observaciones recogen informacion del estado actual y estan relacionadas con la pro-babilidad de este estado. Esta funcion de densidad de probabilidad es modelada por lafuncion O : Z ×A× S → [0, 1], donde O(z, a, s′) = p(zt = z|at−1 = a, st−1 = s), que da laprobabilidad de la observacion z si la accion a ha sido ejecutada y el estado resultante hasido s’.

Funcion de recompensaUn POMDP selecciona las mejores acciones para que la funcion de utilidad sea optimizada.Por lo tanto, el comportamiento del sistema estara determinado por esta funcion, la cualdependera de una funcion de recompensa. R : S × A→ R es esta funcion de recompensa,donde R(s, a) es la recompensa obtenida por la ejecucion de la accion a en el estado s.De hecho, la recompensa puede incluir un coste asociado con la ejecucion de la acciondada. Aquı, se asume que la recompensa esta delimitada. Se pueden modelar metas muycomplejas, por lo que la funcion de recompensa es una herramienta muy poderosa, sucorrecto diseno es fundamental.

Factores horizonte y descuentoEl objetivo del agente es maximizar la recompensa que se espera ganar en un tiempo deter-minado. El horizonte h define este tiempo, especificado mediante el numero de intervalos


temporales sobre el que el agente puede realizar la planificacion. Esto es, maximizar lasuma:

E [h∑

t=0γtrt]

donde, rt es la recompensa en el instante t, E[ ] es la funcion de esperanza matematica(con respecto a los posibles estados) y γ ∈ [0, 1) es el factor de descuento, el cual aseguraque la suma anterior es finita cuando h→∞. Ademas, este factor indica como deben serponderadas las recompensas para los distintos intervalos de tiempo [6].

Para entender mejor todo esto consideremos la idea de un robot que debe alcanzar unobjetivo. Para modelar este problema tendremos las siguientes variables de estado:

pos o: Posicion del objetivo a alcanzar.

enc: Indicara si se ha alcanzado el objetivo o no.

pos r: Posicion actual del robot.

Vamos a suponer que estamos trabajando sobre un area como la siguiente:

Figura 1.1: Area de movimiento

Por lo tanto tenemos 9 valores posibles para las variable pos o y pos r. Para la variable encsolo tenemos dos valores, sı y no.

Necesitaremos conocer tambien las variables de observacion que existen. Estas seran

pos r obs: Indicara la posicion del robot obtenida mediante medicion de sus propiossensores. Esta variable tendra los mismos valores posibles que pos o y pos r.

o obs: Indica si el robot observa al objetivo o no. El robot observara al objetivo solo si seencuentra en alguna posicion adyacente. Los valores posibles para esta variable, al igualque para enc, seran sı o no.

Ademas de las variables necesitamos conocer nuestro espacio de acciones. Tendremos cinco ac-ciones: movimiento hacia el norte, sur, este u oeste, y permanecer en la misma posicion, a lasque llamaremos a norte, a sur, a este, a oeste y a perm. Se puede observar que no todas lasacciones son posibles en todas las posiciones, por ejemplo, si el robot esta en la posicion 1 lasacciones a norte y a oeste no tendran sentido.

1.2 Introduccion a los Procesos de Decision de Markov Parcialmente Observables(POMDP) 5

Para finalizar el problema necesitaremos conocer las funciones de transicion, observacion yrecompensa, las cuales modelaremos con diagramas de decision. Este tipo de representacion defunciones es mas concisa y eficiente que las tablas de decision, ya que pueden fusionan ramasiguales o similares.

Un Diagrama de Decision (DD), tambien llamado arbol de decision, es una estructura enforma de arbol donde cada nodo corresponde a una variable, y de ellos cuelgan otros nodos uhojas. Cada rama se correspondera con un valor de la variable, y cada hoja contendra el valorcorrespondiente de la funcion una vez seguido ese “camino”.

En la siguiente imagen veremos un ejemplo de diagrama de decision para la funcion deprobabilidad de la variable de observacion obj obs.

Figura 1.2: Ejemplo DD funcion de observacion

La figura 1.2 no esta completa por comprension del lector, puesto que bajo cada nodo pos o’cuelga una estructura similar a la que se ve bajo el primero. Los valores de probabilidad se veque son diferentes en la posiciones adyacentes a la de la variable padre, que sı estan mas alejadas.La forma de leer esto serıa la siguiente: siendo 1 la posicion del robot, si el objetivo esta en laposicion 2, la probabilidad de que el sensor nos de una medida positiva, es decir, nos indiqueque hemos encontrado el objetivo, es 0.9.

Ademas de estos componentes tendremos, por supuesto, el valor de descuento y horizonte.

Sobre un ejemplo muy similar al anteriormente desarrollado, sera sobre el que se trabaje eneste documento.

Capıtulo 2Estructura de la librerıa

En este capıtulo se va a explicar detalladamente la estructura interna del codigo. Se vera larelacion de las clases que lo componen, ası como la relacion de archivos donde se encuentranestas clases. A continuacion se puede ver una tabla resumen de esta estructura.

Clases ArchivosDD DD.hpp, DD.cpp

MySet MySet.hpp, MySet.cppConfig Config.hpp, Config.cpp

DDcollection DDcollection.hpp, DDcollection.cppPair Pair.hpp, Pair.cpp

TripletSet TripletSet.hpp, TripletSet.cppTripletConfig TripletConfig.hpp, TripletConfig.cpp

CacheMap CacheMap.hppGlobal Global.hpp, Global.cpp

OP OP.hpp, OP.cppParseSPUDD ParseSPUDD.hpp, ParseSPUDD.cpp

Tabla 2.1: Resumen de clases y archivos

Ademas de los archivos mencionados en la tabla 2.1 existe otro archivo, Types.hpp, quecontiene algunos tipos que se usan en toda la librerıa. El contenido de este archivo se puede vera continuacion:

typedef vector <int > Set;typedef vector <Set > Matrix ;

Listado 2.1: Types.hpp

Los tipos Set y Matrix, que se usan en toda la librerıa, no son mas que un vector y unamatriz de enteros respectivamente.

Ademas de estos dos tipos genericos, las clases Pair, TripletSet y TripletConfig tambiendefinen tipos propios del codigo, cuya existencia se explicara mas adelante.

7

8 CAPITULO 2. ESTRUCTURA DE LA LIBRERIA

Pair: Define una pareja de elementos de tipo DD.

TripletSet: Define una pareja de elementos de tipo DD junto con un elemento de tipoSet.

TripletConfig: Define una pareja de elementos de tipo DD junto con un elemento de tipoMatrix.

En los siguientes apartados se entrara en detalle de las demas clases que existen en la librerıa,ası como en sus atributos y metodos.

2.1. Clase DD

La clase DD (Diagramas de Decision) es una de las clases mas importantes de toda la librerıa,ya que modela el tipo de datos objeto de casi todas las operaciones existentes.

Los DD son diagramas de decision, tambien llamados arboles de decision, cuyas hojas alma-cenan los valores de una funcion definida sobre ciertas variables. Por ejemplo, son un modo derepresentacion de funciones de probabilidad mas compacto que las tablas de probabilidad, yaque varias ramas con el mismo valor y la misma raız pueden fundirse en una.

En la figura 2.1 podemos ver un ejemplo de diagrama de decision binario, con tres variables,x1, x2 y x3, cada una con dos posibles valores, 0 y 1. A la derecha del arbol vemos la tablaque modela.

Figura 2.1: Ejemplo de DD

Los diagramas de decision que se manejan en esta librerıa se utilizan como base para mo-delar problemas basados en POMDPs. En particular, se utilizan para modelar las funciones derecompensa y las funciones de densidad de probabilidad necesarias del problema.

class DD {int var;double val;Matrix config ;Set varSet ;

2.1 Clase DD 9

int numLeaves ;std :: vector <DD > children ;double sum;int type;(...)

Listado 2.2: Atributos de la clase DD

En el Listado 2.2 podemos ver los atributos que tiene la clase DD.

La clase DD modela tanto los nodos del arbol como las hojas, aunque los atributos y laoperaciones que se haran con ellos, dependiendo del tipo de elemento, pueden ser ligeramentediferentes. Para ello existe un atributo type que indica si el elemento es un nodo o una hoja. Latabla 2.2 muestra el agrupamiento de los atributos segun el tipo de elemento y lo que contienen.

Atributos Nodos Hojasvar Identificador de la variable asociada al nodo. 0val -∞ Valor asociado a la hoja.

config Matrix vacıa. Configuracion* asociada a la hoja.varSet Set de variables del arbol por debajo del nodo. Set vacıo.

numLeaves Numero de hojas del arbol por debajo del nodo. 1children Hijos del nodo. Vector vacıo.

sum Suma de los valores de las hojas que hay por debajo del nodo. 0type 1 0

Tabla 2.2: Atributos de la clase DD segun tipo de elemento

* La configuracion de una hoja almacena las ramas padres de las que colgaba anteriormente.Inicialmente esta vacıa y se rellena al realizar ciertas operaciones o simplificaciones en el arboldurante las cuales desaparecen ramas. Esta configuracion contiene las parejas variable-valor quedaban lugar al valor actual de esa hoja. Si la configuracion esta vacıa es porque nunca se hamodificado esa hoja y esta tal como venıa en el diagrama original.

Como todos estos atributos son privados existen metodos getters y setters para cada uno deellos. Ademas de estos metodos tenemos:

Constructores: Existen cinco diferentes (Listado 2.3).

• Constructor por defecto: Genera una hoja con valor cero y configuracion vacıa.

• Constructor copia: Crea un objeto DD a partir de otro.

• Constructor de hoja a partir de un valor: Genera una hoja con el valor indicado yconfiguracion vacıa.

• Constructor de hoja con valor y configuracion dados: Genera una hoja con el valor yla configuracion indicados.

• Constructor de nodo: Genera un nodo para la variable dada y con los hijos indicados.

(...)DD();


DD(const DD&);DD( double val);DD( double val , Matrix config );DD(int var , std :: vector <DD > children );(...)

Listado 2.3: Costructores de la clase DD

Generadores de DDs: Existen tres generadores de objetos de tipo DD (Listado 2.4). Ge-neran elementos del mismo modo que los constructores (a excepcion del constructor pordefecto y el constructor copia). La principal diferencia con los constructores es que loselementos generados con estos metodos son almacenados en las variables globales de lalibrerıa, definidas en la clase Global (ver apartado 2.14), los nodos se almacenan en no-deHashtable y las hojas en leafHashtable.

(...)static DD myNew( double );static DD myNew(double , Matrix );static DD myNew(int , std :: vector <DD >);(...)

Listado 2.4: Generadores de la clase DD

Operadores de comparacion: Se han sobreescrito los operadores == y != para los objetosde tipo DD. Dos objetos de tipo DD solo seran iguales si lo son todos sus atributos (Listado2.5).

(...)bool operator !=( const DD&) const ;bool operator ==( const DD&) const ;(...)

Listado 2.5: Operadores de comparacion de la clase DD

Metodos de impresion: El metodo printSpuddDD imprime el contenido de todo el arbol.Los metodos display imprimen los arboles en el formato necesario para la simulacion.(Listado 2.6)

(...)void printSpuddDD (std :: ofstream & fos);void display ();void display (std :: string space);void display (std :: string space , std :: string prefix );(...)

Listado 2.6: Metodo de impresion de la clase DD

2.2 Clase MySet 11

El formato de impresion es el siguiente:( nombre variable1 (nombre variable2 (nombre valor1) (valor) nombre valor2 (valor)... ) )

Metodo de almacenamiento: El metodo store almacena un objeto DD ya existente (creadomediante el constructor) en los atributos globales nodeHashtable y las hojas en leafHash-table (Listado 2.7).

(...)DD store ();(...)

Listado 2.7: Metodo de almacenamiento de la clase DD

Metodos auxiliares: Ademas de los metodos citados anteriormente, existen otros dos quesirven para calcular la precision (la cantidad de decimales) de numeros dados tanto en tipofloat como en tipo string (Listado 2.8). Estos metodos son necesarios para leer e imprimircompletos los valores de las hojas. El por que ha sido necesaria su creacion se explicara enel capıtulo en que expliquemos las pruebas de funcionalidad.

(...)static int calcPrecision (std :: string n);static int calcPrecision ( double );(...)

Listado 2.8: Metodos auxiliares de la clase DD

Ademas de todo lo mencionado, existen otros dos atritutos que simplemente almacenan unahoja con valor cero y una hoja con valor uno. Hojas de este tipo, se usan (Listado 2.9).

(...)DD DD:: one = DD:: myNew (1);DD DD:: zero = DD:: myNew (0);(...)

Listado 2.9: Atributos publicos de la clase DD

2.2. Clase MySet

La clase MySet es una baterıa de operaciones para trabajar con objetos del tipo Set (vectoresde enteros). Este tipo de datos es muy usado en la librerıa, sobre todo, para almacenar conjuntosde variables (identificadores de variables), por lo que resultan necesarias operaciones tales comobusqueda, union, ordenacion o comparacion de Sets, que son, entre otras, las que forman estaclase.


class MySet {public :static int find(Set s, int item);static std :: string toString (Set s);static std :: string maskToString (Set s, std :: vector <bool > mask);static Set unionNotOrdered (Set s1 , Set s2);static Set unionOrdered (Set s1 , Set s2);static Set remove (Set s, int item);static Set removeIth (Set s, int ith);static Set diff(Set s1 , Set s2);static Set sort(Set s);static Set reverse (Set s);static bool equals (Set s1 , Set s2);

};

Listado 2.10: Clase MySet

Como vemos en el listado 2.10 todos los metodos son estaticos, para que no sea necesaria lainstanciacion de ningun objeto de tipo MySet para usar las operaciones.

Las operaciones que nos proporciona la clase MySet son las siguientes:

static int find(Set s, int item) → Este metodo busca un elemento item en el Set dados. Si item se encuentra en s, find devuelve su posicion dentro del Set y si no lo encuentradevuelve -1.

static std::string toString(Set s) → Este metodo devuelve el contenido del Set enforma de cadena de texto.

static std::string maskToString(Set s, std::vector<bool> mask) → Este metododevuelve una cadena del tipo “[a,b,c]” donde a, b y c son los elementos resultado deenmascarar set con una mascara binaria mask, es decir, los elementos que tengan lasmismas posiciones en el Set que los elementos de la mascara con valor 1.

Ejemplo: s = {1,2,4,5,7,9} mask = {0,1,1,0,1,0} Resultado = [2,4,7]

static Set unionNotOrdered(Set s1, Set s2) → Este metodo realiza la union de dosSets y los almacena en un unico objeto de tipo Set. Al realizar la union no se duplicanelementos iguales.

static Set unionOrdered(Set s1, Set s2) → Este metodo realiza la misma operacionque el metodo anterior con la diferencia de que el Set resultado, en este caso, estara orde-nado.

static Set remove(Set s, int item) → Este metodo elimina un elemento item de s ydevuelve el Set sin ese elemento. Si el elemento item no se encuentra dentro de s, devuelveel mismo Set de entrada.

2.3 Clase Config 13

static Set removeIth(Set s, int ith)→ Este metodo elimina el elemento en la posicionith de set y devuelve el Set sin ese elemento. Si la posicion ith es mayor que el tamano des, devuelve el mismo Set de entrada.

static Set diff(Set set1, Set set2) → Este metodo devuelve la resta de s1 menos s2,es decir, devuelve un Set que contiene los elementos de s1 que no existen en s2. Si s1esta vacıo, diff devolvera un Set vacıo.

static Set sort(Set s) → Este metodo ordena el Set de manera ascendente.

static Set reverse(Set s) → Este metodo invierte el orden del Set.

static bool equals(Set s1, Set s2) → Este metodo comprueba si dos Sets son iguales.Devuelve true en caso de ser iguales y false en caso contrario.

2.3. Clase Config

La clase Config es una baterıa de operaciones para trabajar con objetos del tipo Matrix(matrices de enteros). Este tipo de datos se usan en la librerıa para modelar las configuracionesde las hojas de los arboles de decision, es decir, los “caminos” que se han ido tomando tras ciertasoperaciones para llegar al valor actual de la hoja. Caminos quieren decir parejas variable-valor,y es por esto que estos “caminos” se modelan con matrices de enteros, que tendran dimensiones2xN.

Esta clase proporciona operaciones tales como combinacion, adicion, interseccion o elimina-cion de matrices, entre otras.

class Config {public :static std :: string toString ( Matrix config );static Matrix merge( Matrix config1 , Matrix config2 );static Matrix add( Matrix config , int var , int val);static Matrix extend ( Matrix config , Set vars);static DD convert2dd ( Matrix config , double value);static DD convert2dd ( Matrix config );static Matrix primeVars ( Matrix config , int val);static Matrix removeIth ( Matrix config , int ith);static Matrix intersection ( Matrix config , Set vars);static bool equals ( Matrix config1 , Matrix config2 );

};

Listado 2.11: Clase Config

Al igual que ocurre para la clase MySet, todos los metodos de esta clase son estaticos parapoder utilizarlos sin necesidad de instanciar ningun objeto del tipo Config.

A continuacion describiremos las operaciones que nos proporciona la clase Config:


static std::string toString(Matrix config) → Este metodo devuelve el contenido dela matriz en forma de cadena de texto.

static Matrix merge(Matrix config1, Matrix config2)→ Este metodo combina dosmatrices. Es el equivalente a union en MySet. Devuelve una nueva matriz con los valoresde config1 y config2, si existen valores comunes entre ambas matrices no los duplica.

static Matrix add(Matrix config, int var, int val)→ Este metodo anade una parejavariable valor (var-val) a la matriz config. Si la variable ya estaba contenida en config, sesustituye el valor asociado que tenıa en la matriz por el nuevo valor val.

static Matrix extend(Matrix config, Set vars) → Este metodo amplıa la matrizconfig. Anade las variables indicadas en vars a la matriz que no estuvieran contenidas yaen ella. A estas nuevas variables anadidas les asocia su primer valor, es decir, el valor conidentificado 1 asociado a esa variable.

convert2dd → Como puede verse en el listado 2.11 existen dos versiones de este metodo.

• static DD convert2dd (Matrix config, double value) → En la primera versionse crea un arbol de decision a partir de la configuracion dada por config. Este arbol secrea de la siguiente manera, se crea un nodo por cada variable de config, y de cada unocolgaran tantas hojas como valores posibles tenga la variable, para el valor asociadoa la variable en config se le dara un valor value, mientras que el resto tendra valorcero.

• static DD convert2dd(Matrix config); → En la segunda version, se realiza lamisma operacion que en la primera, pero en este caso value sera el valor por defecto,uno.

static Matrix primeVars(Matrix config, int val)→ Este metodo devuelve una matrizde configuracion que sea igual a la dada en config pero en la que a los identificadores de lasvariables se les ha sumado val. Normalmente, val indica el numero de variables del sistema,para transformar las variables en sus primas o viceversa. Las variables del sistema, y susvariables primas, son numeradas mediante un identificador entero en orden ascendente, porlo que, si tenemos 10 variables en el sistema, la variable con identificador 11 sera la variableprima correspondiente a la primera variable del sistema, el identificador 12 correspondera ala variable prima asociada a la segunda variable del sistema, y ası sucesivamente. Si elparametro val fuese erroneo, este metodo no devolverıa la misma matriz de configuracionpara sus variables primas, si no una matriz de configuracion totalmente diferente, queposiblemente no tendrıa sentido, ya que podrıa darse el caso de existir variables con valoresasociados que no existen para esa variable.

static Matrix removeIth(Matrix config, int ith) → Este metodo elimina la parejavariable-valor en la posicion ith de config y devuelve la matriz sin esa pareja. Si la posicionith es mayor que el numero de columnas de config, devuelve la misma matriz de entrada.

2.4 Clase DDcollection 15

static Matrix intersection(Matrix config, Set vars) → Este metodo devuelve lainterseccion entre config y vars, es decir, devuelve una nueva matriz que contiene lasparejas variable-valor de config cuya variable esta contenida en vars. Si no existiese ningunavariable de config contenida en vars, intersection devolverıa una matriz vacıa.

static bool equals (Matrix config1, Matrix config2) → Este metodo comprueba sidos matrices de configuracion son iguales. Devuelve true en caso de ser iguales y false encaso contrario.

2.4. Clase DDcollection

class DDcollection {public :static std :: vector <DD > removeIth (std :: vector <DD > collection , int& ith

);static std :: vector <DD > add(std :: vector <DD > collection , DD& dd);

};

Listado 2.12: DDcollection

Esta clase implemeta operaciones para trabajar con vectores de elementos de tipo DD. Solotiene dos metodos, el primero, removeIth, elimina el elemento indicado por la posicion ith delvector, y el segundo, add, anade un elemento al vector en la ultima posicion.

2.5. Clase CacheMap

La clase CacheMap implementa mapas hash enlazados (Linked HashMaps). Un mapa es unaestructura de datos que almacena pares clave/valor de manera que por cada clave solo tenemosun valor. Un mapa hash no es mas que un caso particular de estos ordenados a partir de loscodigos hash de las claves, consiguiendo busquedas mas eficientes que en un mapa normal.Una funcion hash es aquella que calcula un codigo hash y que cumple las siguientes condiciones:

Debe ser rapida de calcular.

Dado un elemento ’Y’ debe ser inviable encontrar el elemento X con el que se obtuvo(h(X)=Y). Es decir, debe ser una funcion de un unico sentido.

Dados dos elementos x1 y x2 que sean iguales (x1 = x2), el resultado de aplicar la funcionhash a ambos debe dar el mismo resultado (h(x1) = h(x2)) [7].

Un CacheMap es un mapa hash de tamano limitado que ademas de tener los elementosordenados por sus codigos hash, mantiene referencias al orden con el que fueron introducidos losvalores. Esto es implementado mediante una lista interna en la que se introducen las claves a lavez que se introducen los pares clave/valor en el mapa. Como se observa en la declaracion de la


clase, la base de CacheMap es el unordered map umap, que es un mapa hash, y la lista l, quees quien guarda el orden de entrada de los elementos (ver listado 2.13).

template <class Key , class T>class CacheMap {public :int maxCapacity ;std ::list <Key > l;std :: unordered_map <Key , T> umap;

CacheMap ();CacheMap (int maxCapacity );

bool removeEldestEntry ();T& put(Key&, T&);bool remove ( const Key &);void clear ();};

Listado 2.13: CacheMap

En la primera lınea de la declaracion de la clase, se observa que CacheMap es una plantilla(template), es decir, de datos genericos, donde el tipo de los datos claves sera Key y el tipo delos valores sera T. Es por esto ultimo, por lo que la clase completa se ha implementado en elarchivo de cabecera CacheMap.hpp. para evitar problemas de compilacion.

A continuacion, se van a describir los diferentes atributos y metodos de la clase:

int maxCapacity: Capacidad maxima del CacheMap. El numero de elementos del mapano podra superar este valor.

std::list<Key> l: Lista de las claves ordenada por orden de entrada al mapa.

std::unordered map<Key, T> umap: Mapa hash base de la clase.

CacheMap(): Constructor por defecto de la clase. Inicializa el tamano maximo a un valorde 100000.

CacheMap(int maxCapacity): Constructor que inicializa el tamano maximo al valordado por el argumento.

bool removeEldestEntry(): Metodo que elimina la ultima entrada al mapa si procede, esdecir, si el tamano maximo del mapa ha sido superado. Devuelve true si se habıa superadoel valor maximo, y por tanto se ha borrado el elemento, y false en caso contrario.

T& put(Key&, T&): Metodo de insercion de elementos en el mapa. Devuelve unareferencia al valor introducido al mapa.

2.5 Clase CacheMap 17

bool remove(const Key&): Metodo que elimina el elemento indicado por el argumentodevolviendo true en caso de haberse realizado la operacion y false en caso de no encon-trarse el elemento en el CacheMap.

void clear(): Metodo de limpieza. Este metodo elimina todas las entradas del mapa.

2.5.1. Aspectos importantes en el uso de mapas hash

A la hora de trabajar con los contenedores definidos en la librerıa estandar de C++ (STL),como vector, list o map existen aspectos importantes a tener en cuenta.

Si se utilizan estos contenedores para trabajar con tipos tambien estandar STL no suponenningun problema, pero si se quiere usarlos con tipos de datos definidos por el usuario, estosdeben cumplir dos reglas principales:

Tener definido el constructor copia.

Sobrescribir el operador asignacion.

El por que deben cumplir estas reglas es muy sencillo, la funcionalidad interna de los contenedoreslo requiere. Cuando se usa, por ejemplo un vector, este, internamente en sus metodos, intentallamar al constructor copia y/o hace asignaciones entre elementos del tipo base del vector, esdecir, el tipo definido por el usuario.

Ademas de estas dos reglas, para poder usar contenedores del tipo unordered map, que estanbasados en funciones hash, existe una tercera regla: se debe sobrescribir tambien la plantillade la estructura/clase hash (es indiferente cual se sobrescriba) para cada tipo que se cree.Por ejemplo, en este codigo, para la clase Pair se tiene:

namespace std{template <>class hash <Pair >{

public :std :: size_t operator () ( const Pair& x) const{

DD dd1=x.dd1;DD dd2=x.dd2;return std ::hash <DD >()(dd1)+std ::hash <DD >()(dd2);

}};

}

Tambien se debe indicar a la clase Pair que la clase hash<Pair> es una clase amiga para puedautilizar los elementos privados de la clase Pair. Para ello se introduce en la declaracion de laclase Pair la instruccion:

...friend class std ::hash <Pair >;...


Cumpliendo estas tres sencillas reglas, ya se pueden utilizar tipos de datos definidos por elusuario con cualquier contenedor de la librerıa estandar STL.

Lo anterior se ha implementado para los tipos DD, Pair, TripletConfig y TripletSet.

2.6. Clase Global

La clase Global es la encargada de mantener todas las variables globales del sistema. Estaclase almacena todos los conjuntos de datos y los resultados de operaciones que se van realizandonecesarios para el buen funcionamiento de la librerıa.

En el listado 2.14 se puede observar la declaracion de la clase y, posteriormente, entraremosa describir en detalle cada elemento.

typedef std :: vector <std :: string > VecString ;typedef std :: vector < VecString > MatString ;

class Global {public :static Set varDomSize ;static VecString varNames ;static MatString valNames ;static CacheMap <DD , DD > leafHashtable ;static CacheMap <DD , DD > nodeHashtable ;static CacheMap <Pair , DD > addHashtable ;static CacheMap <Pair , DD > multHashtable ;static CacheMap < TripletConfig , DD > maxHashtable ;static CacheMap < TripletConfig , DD > minHashtable ;static CacheMap <TripletSet , double > dotProductHashtable ;static CacheMap <DD , int > nEdgesHashtable ;static CacheMap <DD , int > nLeavesHashtable ;static CacheMap <DD , int > nNodesHashtable ;static void setVarDomSize (Set newVarDomSize );static void setVarNames ( VecString newVarNames );static void setValNames (int varId , VecString newValNames );static void clearHashtables ();template < typename K, typename V>static Set getKeyHashCodeSet (std :: unordered_map <K,V> hashMap );

};

Listado 2.14: Global

Nota: En lo que respecta al detalle de la clase Global, cuando hablamos de variables nosreferimos a variables de estado, variables de observacion y cada variable prima asociada a cadauna de ellas.

VecString y MatString → Son dos tipos de datos definidos en esta clase por su multipleuso. No son mas que un vector y una matriz de cadenas.

2.6 Clase Global 19

varDomSize → Set que contiene el tamano del dominio de cada variable.

varNames → Conjunto de nombres de todas las variables.

valNames → Matriz que contiene por cada variable los nombres de todos sus posiblesvalores.

leafHashtable → CacheMap que almacena todas las hojas que se van definiendo a lolargo de la ejecucion del programa.

nodeHashtable → CacheMap que almacena todos los nodos que se definen durante laejecucion del programa.

addHashtable → CacheMap que almacena todas las sumas de arboles de decision quese realizan durante la ejecucion del programa. Para una pareja de arboles concreta (unobjeto del tipo Pair) almacena el valor de su suma.

multHashtable → CacheMap que almacena todas las multiplicaciones de DDs que serealizan en el programa.

maxHashtable → CacheMap que para un objeto del tipo TripletConfig almacena el re-sultado de la operacion max de la clase OP con los atributos del TripletConfig comoargumentos de la operacion (ver apartado 2.7).

minHashtable → Este CacheMap es igual que el anterior con la diferencia de que alma-cena los resultado de la operacion min de OP.

dotProductHashtable → CacheMap que almacena el resultado de la operacion dotPro-duct de la clase OP realizada con los atributos de un objeto de tipo TripletSet que va aser la clave del mapa.

nEdgesHashtable→ Para cada arbol que se haya calculado su numero de bordes internos,este CacheMap almacena la pareja arbol - numero de bordes.

nLeavesHashtable → Para cada arbol que se haya calculado su numero de hojas, esteCacheMap almacena la pareja arbol - numero de hojas.

nNodesHashtable → Para cada arbol que se haya calculado su numero de nodos, esteCacheMap almacena la pareja arbol - numero de nodos.

static void setVarDomSize(Set newVarDomSize)→ Setter del atributo varDomSi-ze.

static void setVarNames(VecString newVarNames) → Setter del atributo varNa-mes.

static void setValNames(int varId, VecString newValNames) → Setter del atri-buto valNames.


static void clearHashtables() to Metodo que limpia todos los CacheMaps mencionadosanteriormente.

static Set getKeyHashCodeSet(std::unordered map<K,V> hashMap)→ Metodoque devuelve un vector que contiene los hash de las claves de un mapa hash dado.

Todos estos CacheMap globales sirven para dar eficiencia al programa. Por ejemplo, al al-macenar cada suma de arboles que se realiza nos ahorramos repetir operaciones, ya que antesde realizar una suma siempre se comprobara si se ha realizado anteriormente y esta almace-nada en addHashtable. La busqueda del resultado en el CacheMap es mucho mas eficiente quela repeticion de la operacion, ya que las operaciones con arboles consumen mucha capacidadcomputacional de la CPU.

2.7. Clase OP

La clase OP es la que provee todas las operaciones necesarias para trabajar con DDs. En losparrafos siguientes vamos a ir viendo todas las operaciones que nos ofrece esta clase y como seutiliza cada una.

Operaciones aritmeticas con arboles de decisionclass OP {public :

static DD add(DD dd1 , DD dd2);static DD addN(std :: vector <DD > ddArray );static DD addN(DD dd);

static DD sub(DD dd1 , DD dd2);static DD neg(DD dd);

static DD mult(DD dd1 , DD dd2);static DD multN(std :: vector <DD > ddArray );static DD multN(DD dd);

static DD div(DD dd1 , DD dd2);static DD inv(DD dd);

static DD abs(DD dd);

static std :: vector <std :: vector <double > > dotProduct (std ::vector <DD > dd1Array , std :: vector <DD > dd2Array , Set vars);

static std :: vector <double > dotProduct (DD dd1 , std :: vector <DD > dd2Array , Set vars);

static std :: vector <double > dotProduct (std :: vector <DD >dd1Array , DD dd2 , Set vars);

static double dotProduct (DD dd1 , DD dd2 , Set vars);

2.7 Clase OP 21

static std :: vector <std :: vector <double > >dotProductLeafPrune (std :: vector <DD > dd1Array , std ::vector <DD > dd2Array , Set vars);

static std :: vector <double > dotProductLeafPrune (DD dd1 , std:: vector <DD > dd2Array , Set vars);

static std :: vector <double > dotProductLeafPrune (std :: vector <DD > dd1Array , DD dd2 , Set vars);

static double dotProductLeafPrune (DD dd1 , DD dd2 , std ::vector <int > vars);

static std :: vector <std :: vector <double > > dotProductNoMem (std :: vector <DD > dd1Array , std :: vector <DD > dd2Array , Set

vars);static double dotProductNoMem (DD dd1 , DD dd2 , Set vars);static std :: vector <double > dotProductNoMem (DD dd1 , std ::

vector <DD > dd2Array , Set vars);static std :: vector <double > dotProductNoMem (std :: vector <DD >

dd1Array , DD dd2 , Set vars);(...)

Listado 2.15: Operaciones aritmeticas con arboles de decision

• Suma (add, addN ): Existen tres metodos de suma de arboles de decision. La ope-racion que realizan es exactamente la misma, lo unico que varıa de una a otra es elnumero de arboles a sumar. La principal es la suma de dos arboles, esta operacionrealiza la suma de la siguiente manera: para sumas de dos elementos de tipo hoja, elresultado es una hoja con valor igual a la suma de los valores de los argumentos, y unamatriz de configuracion resultado de la combinacion de las matrices de configuracionde los argumentos; en el caso de que los argumentos sean dos nodos con la mismavariable raız se suman recursivamente los hijos de dichos nodos; en cualquier otro casose realiza la suma recursiva del arbol cuya variable asociada tenga un identificador devariable menor con los hijos del otro argumento de la suma. En la imagen 2.2 vemosun ejemplo grafico de esta suma. Los otros dos metodos de suma, realizan la mismaoperacion, el primero realiza la suma entre N arboles; suma los dos primeros arbolesdel conjunto, al resultado de esta suma le suma el tercero, y ası sucesivamente. Laultima version del metodo es un caso particular en que solo queremos sumar un arbol,por lo que el resultado sera el mismo arbol argumento. Cada vez que se realiza unasuma se almacena en el CacheMap addHashtable. Antes de realizar la suma siemprese comprueba que no este ya almacenada en esta variable, si no lo esta, se realiza lasuma y posteriormente se almacena.

• Resta (sub, neg): La resta de DDs se implementa mediante una negacion y una suma.El metodo neg niega un arbol pasado por parametro, o lo que es lo mismo, los valoresnegativos los convierte en positivos y los positivos en negativos. El metodo sub, que


Figura 2.2: Ejemplo de suma de DDs

realiza la resta de dos DDs, simplemente hace la suma del primer argumento con lanegacion del segundo.

• Multiplicacion (mult, multN ): Hay dos versiones de la operacion de multiplicacionque solo se diferencian en el numero de arboles que queremos multiplicar, uno mul-tiplica dos arboles y el otro multiplica todos los elementos de un vector de arboles.El segundo metodo se basa en el primero para realizar las multiplicaciones por loque vamos a explicar como realiza la operacion la primera version del metodo, mult.Como vimos en el detalle de la clase Global, existe un CacheMap que almacena losresultados de multiplicaciones ya realizadas, multHashtable. Debido a esto, lo pri-mero que hace este metodo es comprobar que la multiplicacion que queremos realizarno se haya hecho ya antes; si no esta ya almacenada la operacion, se realiza de lasiguiente manera:

◦ Si los dos elementos pasados como argumentos son elementos de tipo hoja, elresultado es otra hoja cuyo valor es igual a la multiplicacion de los valores de losargumentos, y cuya configuracion es la combinacion de las configuraciones de losargumentos.◦ Si alguno de los elementos es tipo nodo, se realiza la multiplicacion recursiva

del elemento con identificador de variable inferior con cada hijo del nodo conidentificador de variable superior.◦ Si ambos elementos son nodos asociados a la misma variable se realiza la multi-

plicacion recursiva hijo a hijo de cada nodo.

• Division (div, inv): Analogamente a la resta, la division se realiza mediante unamultiplicacion y una inversion. El metodo inv realiza la inversion de un arbol, esdecir, sustituye todos sus valores por sus inversos. La division que realiza el metodo

2.7 Clase OP 23

inv no es mas que la multiplicacion del primer argumento por el inverso del segundo.

• Valor absoluto (abs): Este metodo calcula el valor absoluto de un arbol, o lo quees lo mismo, cambia los valores de sus hojas por el valor absoluto de dichos valores.

• Producto escalar : Existen tres tipos de productos escalares en la clase OP.

◦ dotProduct: Como ya se vio en el apartado 2.6, existe un CacheMap que almacenalos resultado de la operacion dotProduct, dotProductHashtable. Lo primero quecomprueba este metodo es si la operacion ya habıa sido realizada y almacenada endicha variable global, si es ası devuelve el resultado almacenado, si no comienzaa realizar la operacion. El producto escalar de dos arboles no es mas que lamultiplicacion elemento a elemento de los dos arboles y la posterior suma deestas multiplicaciones, dando lugar ası a un unico numero. Las cuatro versionesde este metodo que existen en la librerıa solo se diferencian entre ellas en elnumero de arboles en sus argumentos. Para poder realizar esta operacion sedebe pasar como argumento de la operacion el Set vars que contendra todas lasvariables implicadas en los dos arboles.◦ dotProductNoMem: Este conjunto de metodos realizan exactamente la misma

operacion que dotProduct con la diferencia de que los resultados derivados deestas operaciones no son almacenados en dotProductHashtable.◦ dotProductLeafPrune: En este caso se realiza un producto escalar un poco parti-

cular, se realiza la multiplicacion de cada valor de las hojas del primer argumentopor la suma de los valores de las hojas del segundo argumento y, posteriormente,se suman los resultados. Al igual que en los casos anteriores, la diferencia entrelas versiones distintas del metodo es el numero de arboles argumento, y tambiennecesita un argumento con el set de variables de los arboles implicados en laoperacion.

Operaciones de eliminacion de nodos(...)static DD addout (DD dd , int var);static DD maxout (DD dd , int var);static DD minout (DD dd , int var);

static DD addMultVarElim (std :: vector <DD > dds , Set vars);static DD addMultVarElim (DD dd , Set vars);static DD addMultVarElim (std :: vector <DD > dds , int var);static DD addMultVarElim (DD dd , int var);

static DD addMultCutSet (std :: vector <DD > dds , DD dd , Setvars);

static DD maxAddVarElim (std :: vector <DD > dds , Set vars);static DD maxAddVarElim (DD dd , Set vars);static DD minAddVarElim (std :: vector <DD > dds , Set vars);static DD minAddVarElim (DD dd , Set vars);


static int selectVarGreedily (std :: vector <DD > ddArray , Setvars);

(...)

Listado 2.16: Operaciones de eliminacion de nodos

• addout: Este metodo elimina una variable del arbol mediante la conversion de larama del arbol correspondiente en una hoja con valor igual a la suma de los valoresque hay bajo el nodo que se quiere eliminar.

• maxout: Al igual que el metodo anterior, maxout tambien elimina una variable delarbol, con la diferencia de que convierte la rama de la variable eliminada en una hojacon el valor maximo de las hojas bajo el nodo eliminado.

• minout: De manera analoga al metodo anterior, este elimina la variable y conviertesu rama en una hoja con el valor mınimo de los valores de las hojas bajo el nodoeliminado.

• addMultVarElim: En la version completa del metodo, static DD addMultVarElim(std::vector<DD> dds, Set vars), se eliminan las variables vars de todos los arbolescontenidos en dds. La eliminacion de cada variable se hace mediante el metodo addouty se almacenan los resultado en un vector. El metodo devuelve un unico DD que es elresultado de la multiplicacion de los arboles de dicho vector. Las diferentes versionesdel metodo se distinguen entre ellas en el numero de variables a eliminar y en losarboles sobre los que se aplica la operacion.

• addMultCutSet: Este metodo funciona de manera parecida a addMultVarElim, eli-minando variables y sumando los arboles resultantes, pero ademas anade una multi-plicacion por otro arbol adicional.

• maxAddVarElim: Este metodo elimina todas las variables de vars de los arboles dedds con el metodo maxout y posteriormente suma todos los resultados para devolverun unico DD. Las diferentes versiones del metodo se diferencian unicamente en elnumero de arboles sobre los que se aplica el metodo.

• minAddVarElim: Este metodo es analogo al anterior, con la diferencia de que elmetodo que se usa para la eliminacion de variables es minout.

• selectVarGreedily: Este metodo es usado por varios de los anteriores para decidirque variable es mas eficiente eliminar primero.

Calculo de propiedades de arboles

(...)static DD extractConfig (DD dd , Set vars);static DD clearConfig (DD dd);static int getNumLeavesDepth (DD dd);

2.7 Clase OP 25

static std :: vector <double > enumerateLeaves (DD dd);static int nEdges (DD dd);static int nLeaves (DD dd);static int nNodes (DD dd);static DD findLeaf (DD dd , DD leaf);(...)

Listado 2.17: Calculo de propiedades de arboles

• extractConfig: Este metodo recorre el arbol y extrae la configuracion de las hojasque no la tengan vacıa. Estas hojas las convierte en un arbol que vale 1 para dichaconfiguracion y 0 en otro caso. El parametro vars debe contener aquellas variables queexisten en el arbol del que vamos a extraer la configuracion. A continuacion vamos aver un ejemplo:

Supongamos que hemos aplicado la operacion maxout para eliminar la variable x2del primer arbol que se ve en la imagen 2.3. Los recuadros que se ven bajo las hojasdel resultado de la aplicacion son sus matrices de configuracion (identificador de lavariable, x2 en este caso, y valor).

Figura 2.3: Ejemplo de maxout

Ahora, a este resultado vamos a aplicarle la operacion extractConfig, y quedarıa loque vemos en la imagen 2.4.

Figura 2.4: Ejemplo de extractConfig


• clearConfig: Este metodo borra la configuracion de un arbol, es decir sustituye todassus hojas por hojas con el mismo valor pero configuracion vacıa.

• getNumLeavesDepth: Este metodo devuelve la suma de los atributos numLeaves detodos los nodos que contiene el arbol. Es decir, es el resultado de aplicarle el metodogetNumLeaves a cada nodo del arbol.

• enumerateLeaves: Este metodo devuelve un vector que contiene todos los valoresde las hojas de un arbol.

• nEdges: Este metodo calcula la cantidad de ramas diferentes (lıneas, si lo vemosgraficamente) de un arbol. Por ejemplo, para el segundo arbol de la imagen 2.4 elmetodo nEdges devolverıa 8.

• nLeaves: Este metodo calcula el numero de hojas diferentes de un arbol. Siguiendocon el ejemplo anterior, para el segundo arbol de la imagen 2.4 este metodo devolverıa2. Este metodo es diferente de getNumLeavesDepth, ya que este ultimo devolverıa 24hojas, que son las que hay realmente en el arbol.

• nNodes: Este metodo calcula el numero de nodos diferentes de un arbol.Para elsegundo arbol de la imagen 2.4 este metodo devolvera 4.

• findLeaf : Este metodo busca una hoja concreta dentro de un arbol. Devuelve unarbol con la misma estructura en el que las hojas que corresponderıan con la buscadatienen valor 1, y las demas valor 0

Figura 2.5: Calculo de nEdges, nLeaves, nNodes y getNumLeavesDepth

2.7 Clase OP 27

Modificacion de arboles(...)static DD primeVars (DD dd , int n);static std :: vector <DD > primeVarsN (std :: vector <DD > dds , int

n);

static std :: vector <DD > swapVars (std :: vector <DD > ddArray ,Matrix varMapping );

static DD swapVars (DD dd , Matrix varMapping );

static DD replace (DD dd , double val1 , double val2);

static DD orderLast (DD dd , int varId);static DD reorder (DD dd);

static DD approximateAll (DD dd , double tolerance );static DD approximate (DD dd , double tolerance );static DD approximate (DD dd , double tolerance , double

prescribedLeafVal );static DD approximate (DD dd , double tolerance , std :: vector <

double > prescribedLeafValues );

static std :: vector <double > convert2array (DD dd);static std :: vector <std :: vector <double > > convert2array (std

:: vector <DD > ddArray , Set varList );static std :: vector <double > convert2array (DD dd , Set varList

);(...)

Listado 2.18: Modificacion de arboles

• Arbol primado (primeVars): Este metodo funciona de igual forma que el metodoprimeVars de la clase Config. Dado un arbol concreto, sustituye todas las variablesde este por sus variables primas. Para que esto sea posible es necesario pasarle ala funcion un parametro n. El identificador de cada variable se desplazara segun lacantidad indicada en este parametro. El metodo primeVars realiza esta operacionsobre un arbol, mientras que primeVarsN realiza la misma operacion sobre N arbolesindicados en un vector pasado como argumento del metodo.

• Permutacion de variables (swapVars): A partir de una matriz 2xN que contieneparejas de permutaciones de variables se modifican los arboles pasados por argumento.Se comprueba que variables del arbol/es parametro se encuentran en la matriz, y seprocede a permutar esas variables por la indicada en varMapping. Tras realizar todaslas permutaciones necesarias se reordena el arbol con el metodo reorder.

• Sustitucion de variables (replace): El metodo static DD replace(DD dd, doubleval1, double val2) sustituye todas las hojas de un arbol dado que tengan un ciertovalor val1 por el valor val2.


• Ordenacion: Tenemos dos formas diferentes de alterar el orden de un arbol.◦ Poner una variable concreta como raiz: El metodo static DD orderLast(DD

dd, int varId) reordena el arbol de manera que la variable identificada por varIdsea la raiz del arbol dado dd.◦ Orden descendente: El metodo static DD reorder(DD dd) modifica el arbol

ordenando sus nodos de mayor a menor identificador de variable, la variable raizsera la de identificador mas alto.

• Aproximacion: El conjunto de metodos approximate aproximan los valores de lashojas cercanos entre sı o a ciertos valores dados cumpliendo una tolerancia configu-rable.◦ static DD approximate(DD dd, double tolerance): Esta es la version mas

basica del metodo. Recorre el arbol y comprueba si existen valores en el arbol quese diferencien entre sı en una cantidad menor a tolerance, si es ası los aproximatodos al mismo valor.◦ static DD approximate(DD dd, double tolerance, double prescribed-

LeafVal): En esta version del metodo se comprueba si los valores de las hojasdel arbol se aproximan, con una tolerancia tolerance, al valor prescibredLeafVal.Si es ası se sustituyen estos valores por el dado.◦ static DD approximate(DD dd, double tolerance, std::vector<double>

prescribedLeafValues): Esta version realiza la misma operacion que la anterior,pero busca varios valores con los que comparar en vez de uno dado en el vectorprescribedLeafValues.◦ static DD approximateAll(DD dd, double tolerance): Esta version es algo

diferente. Entre las diferentes hojas hijas de cualquiera de los nodos del arbolcomprueba que los valores difieran entre ellas una cantidad mayor a la tolerancia,si no es ası, modifica todos los valores del conjunto y les da el valor medio entreellos, es decir, calcula la media entre el mayor y menor valor del conjunto y esees el valor que les da a todas las hojas hermanas.

• Conversion de arbol en vector : Los metodos convert2array devuelven el arbol oarboles pasados por parametros en forma de vector. El vector contiene los valores delarbol para todas las combinaciones posibles de las variables en varList (por defecto,las variables del arbol). El argumento varList debe contener, como mınimo, todas lasvariables del arbol. Ası, en el vector de salida podremos leer el valor de la funcioncodificada en el arbol para cada combinacion de variables de entrada.

Operaciones estadısticas(...)

static double factoredExpectationSparse (std :: vector <DD >&factDist , DD dd);

static std :: vector < std :: vector <double > >factoredExpectationSparse (std :: vector <std :: vector <DD >>& factDist , std :: vector <DD > ddArray );

2.7 Clase OP 29

static std :: vector <double > factoredExpectationSparse (std ::vector <std :: vector <DD > >& factDist , DD dd);

static std :: vector <std :: vector <double > >factoredExpectationSparseNoMem (std :: vector <std :: vector <DD > >& factDist , std :: vector <DD > ddArray );

static std :: vector <double > factoredExpectationSparseNoMem (std :: vector <DD >& factDist , std :: vector <DD > ddArray );

static std :: vector <double > factoredExpectationSparseNoMem (std :: vector <std :: vector <DD > >& factDist , DD dd);

static double factoredExpectationSparseNoMem (std :: vector <DD>& factDist , DD dd);

static std :: vector <std :: vector <double > >factoredExpectationSparseParallel (std :: vector <std ::vector <DD > >& factDist , std :: vector <DD > ddArray );

static std :: vector <double >factoredExpectationSparseParallel (std :: vector <std ::vector <DD > >& factDist , DD dd);

static std :: vector <std :: vector <double > >factoredExpectationSparseParallel2 (std :: vector <std ::vector <DD > >& factDist , std :: vector <DD > ddArray );

static std :: vector <double >factoredExpectationSparseParallel2 (std :: vector <std ::vector <DD > >& factDist , DD dd);

static std :: vector <double > factoredExpectationParallel (std:: vector <std :: vector <DD > >& factDist , DD dd);

static int sampleMultinomial (std :: vector <double > pdist);static Matrix sampleMultinomial (std :: vector <DD > ddArray ,

Set varSet );static Matrix sampleMultinomial (DD dd , Set varSet );static Matrix sampleMultinomial (DD dd , int varId);(...)

Listado 2.19: Operaciones estadısticas

• Valor esperado:

◦ factoredExpectationSparse: Este metodo calcula el valor esperado de uno o va-rias funciones codificadas en forma de arboles. Admite como parametros, ademasde uno o varios arboles de decision sobre los que se calculara el valor esperado,un vector o matriz de arboles que van a contener las distribuciones de probabi-lidad para cada variable (factores). Internamente, se llama a un metodo privadorecursivo que es quien realmente realiza la operacion y almacena los resultadosde las operaciones que hace en cada llamada en un unordered map. Tiene tresvariantes diferenciadas por sus parametros:


1. Un vector de arboles con distribuciones de probabilidad y un unico arbol.Devuelve un unico valor decimal.

2. Una matriz de arboles con distribuciones de probabilidad y un unico arbol.Devuelve un vector de valores decimales, cada uno de ellos el valor esperadodel arbol parametro pero para diferentes vectores de arboles de probabilidad,uno por cada fila de la matriz.

3. Una matriz de arboles con distribuciones de probabilidad y un vector de arbo-les. Devuelve una matriz de valores esperados, emparejando cada elementodel vector de arboles con las filas de la matriz de arboles de probabilidad.

◦ factoredExpectationSparseNoMem: Este metodo realiza la misma operacionque el anterior sin utilizar el mapa hash para almacenar los resultados. Es decir,los calcula cada vez aunque ya hayan sido calculados antes. Este metodo es maslento que el anterior. En este caso existe una version mas del metodo que enel caso anterior en el que se calcula el valor esperado de un vector de arbolesdiferentes con el mismo vector de probabilidades. Esta version devuelve un vectorde valores, uno por cada arbol del vector.◦ factoredExpectationSparseParallel: Este metodo es una version de factore-

dExpectationSparse que admite como parametro una matriz de arboles de pro-babilidades donde solo se calcula los factores esperados para variables que enla matriz de probabilidades no tienen valor 0. Tiene dos versiones iguales a lasegunda y la tercera version de factoredExpectationSparse.◦ factoredExpectationSparseParallel2 : Este metodo realiza la misma opera-

cion que el anterior pero almacenando los resultados en una variable interna,para darle mayor eficiencia y rapidez.◦ factoredExpectationParallel: Este metodo realiza el calculo del valor esperado

de igual forma que el primero de esta lista con la diferencia de que no almacenalos resultados en su mapa interno valor a valor, si no que almacena un vector devalores cada vez. Es decir, almacena el vector de los valores esperados del arboldado por argumento para cada fila de la matriz de probabilidades en un vectory este vector es el que se almacena en el mapa.

• Muestreo (sampleMultinomial): Este conjunto de metodos devuelve una muestraaleatoria del valor de una o varias variables de acuerdo con la distribucion de proba-bilidad contenida en un arbol.

Maximo y mınimo(...)static DD threshold (DD dd , double val , int parity );

static DD max(DD dd1 , DD dd2);static DD max(DD dd1 , DD dd2 , Matrix config );static DD maxN(std :: vector <DD > ddArray );static DD maxN(DD dd);

2.7 Clase OP 31

static DD min(DD dd1 , DD dd2);static DD min(DD dd1 , DD dd2 , Matrix config );

static bool maxNormDiff (DD dd1 , DD dd2 , double threshold );(...)

Listado 2.20: Maximo y mınimo

• Umbralizacion: Este metodo comprueba si los valores de un arbol estan por debajoo por encima de un umbral.

◦ parity > 0 → Si los valores de las hojas del arbol son menores que val devuelveuna hoja de valor 0, en caso contrario devuelve el arbol de entrada sin modificar.◦ parity < 0 → Si los valores de las hojas del arbol son mayores que val devuelve

una hoja de valor 0, en caso contrario devuelve el arbol de entrada sin modificar.◦ parity = 0 → Si los valores de las hojas del arbol iguales a val devuelve una hoja

de valor 0, en caso contrario devuelve el arbol de entrada sin modificar.

• Arbol maximo: Este metodo compara ambos arboles y crea uno nuevo con losvalores maximos. Si la operacion ha sido realizada antes estara almacenada en lavariable global maxHashtable, por lo que antes de realizar la operacion siempre secomprueba si ya se ha realizado antes para evitar operaciones innecesarias, si noesta almacenado el resultado de la operacion que buscamos, entonces se calcula.

• Arbol mınimo: Este metodo compara ambos arboles y crea uno nuevo con los valoresmınimos. Si la operacion ha sido realizada antes estara almacenada en la variableglobal minHashtable, por lo que antes de realizar la operacion siempre se compruebasi ya se ha realizado antes para evitar operaciones innecesarias, si no esta almacenadoel resultado de la operacion que buscamos, entonces se calcula.

• Umbralizacion de la diferencia: Este metodo calcula la diferencia entre los dosarboles pasados como argumentos y si el valor absoluto de los valores de las hojasde este arbol diferencia estan por debajo del umbral devuelve true en caso contrariodevuelve false.

Restriccion y evaluacion de arboles

(...)static DD restrict (DD dd , Matrix config );static DD restrictOrdered (DD dd , Matrix config );static std :: vector <DD > restrictN (std :: vector <DD > dds ,

Matrix config );static std :: vector <DD > restrictN (DD dd , Matrix config );

static double eval(DD dd , Matrix config );static std :: vector <double > evalN(std :: vector <DD > dds ,

Matrix config );


static std :: vector <double > evalN(DD dd , Matrix config );(...)

Listado 2.21: Restriccion de arboles

• Restriccion de uno o varios arboles: El primer conjunto de metodos restringe uno ovarios arboles a una configuracion dada por config. En concreto, se particulariza elarbol para los valores de las variables incluidos en config. El metodo restricOrderedademas de ejecutar la restriccion reordena los arboles.

• Evaluacion de una configuracion: El segundo conjunto de metodos evalua uno o variosarboles para una configuracion dada y devuelve el valor correspondiente.

Operaciones de impresion

(...)static void printPolicySpuddFormat (std :: string filename ,

std :: vector <DD > valuef , Set pol);static void printPolicySpuddFormat (std :: string filename , DD

avec , int pol);static std :: string displaySpuddFormat (DD dd , int

indentation );static std :: string displaySpuddFormat (DD dd , int

indentation , int primedVarId );static void displaySpuddFormat (std :: string fileName , DD dd ,

std :: string indentation , int primedVarId );static void displaySpuddFormat (std :: ofstream & fos , DD dd ,

std :: string indentation , int primedVarId );(...)

Listado 2.22: Operaciones de impresion

Otras operaciones

(...)static Matrix setupIP (DD dd , Set var2row , int colId);

static std :: vector <DD > marginals (std :: vector <DD > cpts , SetmargIds , Set summoutIds );

static double maxabs (std :: vector <double > t);static std :: vector <double > getMax (std :: vector <std :: vector <

double > > pbv);static std :: vector <double > getMax (std :: vector <std :: vector <

double > > pbv , Set pids);static std :: vector <double > getMax (std :: vector <std :: vector <

double > > pbv , int len , Set pids);

static double maxAll (DD dd);

2.8 Clase ParseSPUDD 33

static double maxAllN (DD dd);static std :: vector <double > maxAllN (std :: vector <DD > dds);

static double minAll (DD dd);static double minAllN (DD dd);static std :: vector <double > minAllN (std :: vector <DD > dds);

static std :: vector <double > sub(std :: vector <double > t1 , std:: vector <double > t2);

Listado 2.23: Otras operaciones

A continuacion, se detallan ciertos metodos auxiliares que son necesarios para la ejecucionde las operaciones anteriormente indicadas:

• setupIP: Dado un arbol de entrada, devuelve una matriz con informacion de confi-guracion especial para todas las hojas.

• marginals: Calcula las distribuciones de probabilidad marginales de un arbol paravarias variables. Dado un arbol con una funcion de probabilidad con varias variablesP(X, Y, Z) devuelve un vector de arboles con las funciones de probabilidad marginalespara cada variable P(X), P(Y), P(Z).

• Maximos

◦ maxabs: Devuelve el valor absoluto maximo de un conjunto de numeros deci-males.◦ getMax: Este metodo devuelve el valor maximo de una matriz de numeros deci-

males. En su version mas sencilla busca en toda la matriz, en la segunda versionbusca unicamenet en ciertas filas de la matriz, el parametro pids indica los identi-ficadores de las filas en las que queremos buscar. En la ultima version del metodo,la mas compleja, busca el maximo en las filas indicadas y para un numero de co-lumnas indicado en len.◦ maxAll, maxAllN : Estos metodos devuelven el valor maximo dentro de uno o

varios arboles.

• Mınimos (minALL, minAllN): Estos metodos devuelven el valor mınimo dentrode uno o varios arboles.

• sub: Este metodo devuelve la diferencia elemento a elemento entre dos vectores dedoubles.

2.8. Clase ParseSPUDD

La clase ParseSPUDD esta dedicada a la lectura de ficheros que contienen definiciones demodelos POMDPs. Por tanto, se encarga de leer las variables, acciones, arboles de decision,


belief inicial, y el resto de elementos necesarios para modelar un problema basado en POMDP.Una vez cargado el modelo, la librerıa permite la realizacion de todas las operaciones detalladasanteriormente.

Para describir el funcionamiento de esta clase, comenzaremos viendo un ejemplo de ficherode entrada.

( variables( nombre_variable_estado1 nombre_valor1 nombre_valor2 ... )( nombre_variable_estado2 nombre_valor1 nombre_valor2 ... )...)( observations( nombre_variable_observacion1 nombre_valor1 nombre_valor2 ... )( nombre_variable_observacion2 nombre_valor1 nombre_valor2 ... )...)

init [*arbol_belief_marginal1arbol_belief_marginal2...]

dd nombre_arbol1( nombre_variable ( nombre_valor ( nombre_variable ( nombre_valor

( valor_numerico )) ( nombre_valor ( valor_numerico )) ...)... ))

enddd

dd nombre_arbol2...enddd

...

action nombre_accion1nombre_variable_estado1 ( arbol1 )nombre_variable_estado2 ( arbol2 )...

observenombre_variable_observacion1 ( arbol_obs1 )...endobserve

cost ( valor_coste )endaction


action nombre_accion2...endaction

...

reward [+ (arbol) ]discount valor_discounttolerance valor_tolerancehorizon valor_horizon

Listado 2.24: Fichero de entrada

Como se ve en el listado 2.24, el fichero de entrada comienza definiendo las variables de estado yobservacion del problema. Despues define la creencia o belief inicial (init), para posteriormentedefinir todos los diagramas de decision posibles del problema, y las acciones que puede realizarel agente. Al final del archivo se definen la recompensa (reward), el descuento (discount), latolerancia (tolerance) y el horizonte (horizon) del POMDP correspondiente.

A continuacion mostramos los atributos publicos de la clase ParseSPUDD y detallaremosque son y para que sirven cada uno.

string buffer ;unordered_map <std :: string , DD > existingDds ;std :: vector <std :: string > varNames ;std :: vector <std :: vector <std :: string > > valNames ;vector <std :: string > actNames ;std :: vector <std :: string > adjunctNames ;std :: vector <std :: vector <DD > > actTransitions ;std :: vector <std :: vector <DD > > actObserve ;std :: vector <DD > actCosts ;std :: vector <DD > adjuncts ;DD reward ;DD init;DD discount ;DD tolerance ;DD horizon ;bool unnormalized ;int nStateVars ;int nObsVars ;

Listado 2.25: ParseSPUDD

buffer : En buffer se guarda el texto una vez leıdo y procesado. Entendemos por procesar,quitar los comentarios y separar correctamente los elementos del archivo para que puedaleerse correctamente.

existingDds: Este atributo almacena todos los arboles existentes en el fichero. Es un


mapa cuya clave es el nombre del arbol, y su valor, el arbol en sı.

varNames: En este vector de cadenas almacenamos los nombres de todas las variablesdel problema.

valNames: Esta matriz de cadenas almacena los nombres de todos los valores que puedentomar las variables del problema. Cada fila corresponde a una variable.

actNames: En este atributo se almacenan los nombres de todas las acciones posibles delagente.

adjunctNames: En este vector se almacenan los nombres de todos los adjuntos definidospara el problema. Los adjuntos son belief iniciales alternativos que se pueden utilizar parael calculo de polıticas del POMDP. Por defecto, solo se utilizarıa el belief inicial, y losadjuntos son opcionales.

actTransitions: Este atributo es una matriz de arboles que almacena las transiciones deestado debidas a las acciones realizadas por el agente. Por cada fila almacena las transi-ciones debidas a una accion.

actObserve: Esta matriz almacena los arboles de observacion de cada accion. Cada filade la matriz corresponde a una accion.

actCosts: Cada accion tiene un arbol de coste asociado. Este vector almacena dichosarboles.

adjuncts: Este atributo almacena los adjuntos del problema.

reward: Arbol de recompensa del problema.

init: Arbol que almacena el belief inicial.

discount: Arbol que almacena el parametro de descuento del problema.

tolerance: Este arbol almacena el valor de tolerancia.

horizon: Este parametro almacena el parametro horizonte.

unnormalized: Este parametro indica si el problema esta normalizado o no.

nStateVars: Este parametro contiene el numero de variables de estado que existen.

nObsVars: Este parametro contiene el numero de variables de observacion que existen.

En el listado siguiente vemos los metodos publicos de esta clase.

ParseSPUDD (char* fileName );void parsePOMDP (bool fullyObservable );void parseVariables ();void parseObservations ();


void parseDDdefinition ();DD parseDD ();void parseAdjunct ();void parseAction ();void parseReward ();void parseInit ();void parseDiscount ();void parseHorizon ();void parseTolerance ();void createPrimeVars ();static bool isWord (std :: string );static bool isNumber (std :: string );std :: string readNoCom (char *);void printPOMDP ();int calcPrecision (std :: string );

Listado 2.26: ParseSPUDD

Constructor: El constructor de la clase admite como parametro el nombre del archivo quese debe leer y se encarga de leerlo y almacenarlo en buffer e inicializar algunos parametros:init es inicializada a una hoja de valor 1, reward a una hoja de valor 0, unnormalized sele da valor false, y los atributos nStateVars y nObsVars a 0.

Metodos de analisis:

• parsePOMDP: Este metodo es el principal de la clase. Es el que se encarga de irrecorriendo la cadena buffer que contiene el contenido del fichero e ir identificando losdiferentes componentes para posteriormente llamar al metodo especıfico de lectura.

• parseVariables: Este es el metodo especıfico para la lectura de las variables de estadodel problema y sus valores. Los almacena en varNames y valNames, respectivamente.

• parseObservations: Este metodo lee las variables de observacion, ası como sus va-lores, y los almacena tambien en varNames y valNames.

• parseDDdefinition: Este metodo es llamado cada vez que se encuentra la palabraclave dd en el fichero. Se encarga de almacenar el nombre del arbol en existingDds yllamar a parseDD que es quien realmente lee los diagramas de decision.

• parseDD: Este es el metodo que se encarga de leer cada arbol de decision, una vezformado el arbol completo lo devuelve.

• parseAdjunct: Este metodo se encarga de leer los adjuntos del problema. Los alma-cena en adjuncts y sus nombres en adjunctNames.

• parseAction: Este es el metodo especıfico que lee las acciones, guarda sus nombresen actionNames, y guarda las acciones leıdas en actions.

• parseReward: Este metodo es quien lee el arbol recompensa del problema y loalmacena en reward.


• parseInit: Este metodo lee el belief inicial y lo almacena en init.

• parseDiscount: Este metodo es el encargado de leer el descuento del problema yalmacenarlo en discount.

• parseHorizon: Este metodo lee el horizonte y lo almacena en el parametro horizon.

• parseTolerance: Este metodo lee el valor de tolerancia y lo almacena en tolerance.

Otros metodos

• createPrimeVars: Una vez leıdas las variables de observacion y estado, parse-POMDP llama a este metodo para generar las variables primas del problema, que noson mas que las mismas que ya tenemos a las que le anadimos ’ al final del nombre.Las variables primas se utilizan para diferenciar una misma variable antes y despuesde tomar una accion y/o una observacion.

• isWord: Este metodo indica si la cadena pasada como parametro es una palabra ono. Se admiten como caracteres dentro de una palabra los siguientes: ’ ’ y ’ \’. Si elparametro es una palabra isWord devuelve true y en caso contrario devuelve false.

• isNumber : Este metodo devuelve true si la cadena dada como argumento es unnumero, ya sea entero o decimal, y false en caso contrario.

• readNoCom: Este metodo es el que se encarga de “limpiar” el fichero, es decir,eliminar los comentarios e introducir espacios entre palabras y parentesis para que lalectura posterior del buffer se haga correctamente. Tras analizar y modificar el ficherolo devuelve como una cadena.

• printPOMDP: Este metodo imprime todos los atributos tal y como fueron leıdos.

Capıtulo 3Pruebas funcionales y simulacion

Una vez introducida la librerıa, veremos cual ha sido el procedimiento para probar el correctofuncionamiento de todas las operaciones incluidas en ella. Tras esto, mostraremos una simulacioncon un POMDP ejemplo en el que un robot va realizando acciones y tomando observaciones.Las acciones y observaciones las iremos introduciendo manualmente, para ver como evolucionael belief o creencia del robot sobre su estado. Se usara la librerıa descrita para leer el modeloPOMDP de ejemplo y para realizar todos los calculos en tiempo real sobre los diagramas dedecision que modelan el problema.

3.1. Pruebas funcionales

En este Proyecto se partıa de una librerıa original escrita en Java, la cual se ha implementadoen C++. Por tanto, se han utilizado los resultados de operaciones en la librerıa original Javapara comprobar el correcto funcionamiento de la nueva librerıa desarrollada. El procedimientogeneral que se ha seguido para probar el codigo es el siguiente:

1. Ejecucion de una operacion concreta con la librerıa en Java.

2. Impresion del resultado de la operacion en un fichero de texto, ası como de los argumentosnecesarios para realizarla.

3. Lectura de dicho fichero desde la librerıa en C++.

4. Ejecucion de la misma operacion con los mismos argumentos con nuestra librerıa.

5. Comprobacion de resultados comparandolos con los leıdos del fichero.

Para realizar las pruebas funcionales, se ha creado un fichero principal con su funcion main,que implementa un menu para elegir que prueba queremos realizar. Todas las operaciones serealizaron con arboles y elementos pertenecientes al fichero de ejemplo que se utiliza en la Seccion3.2.

39

40 CAPITULO 3. PRUEBAS FUNCIONALES Y SIMULACION

Las diferentes operaciones se han agrupado por logica conceptual, es decir, por cercanıa enel tipo de operacion, con lo que finalmente han quedado las 14 pruebas diferentes que vemos acontinuacion. Para cada una detallamos si ha habido algun tipo de anormalidad en su ejecucion.

Prueba 0: LECTURA POMDPRealiza la lectura y analisis de un fichero de entrada dado como argumento al progra-ma. Con esta prueba garantizamos el correcto funcionamiento de los metodos de la claseParseSPUDD.

Esta prueba se hizo de una manera algo diferente a las demas. Para probar que se realizala lectura y el analisis del fichero correctamente, una vez finalizada se procedio a imprimirtodos los componentes del problema en un fichero para compararlos visualmente con elfichero de entrada. Hecha esta comprobacion y viendo que estaba todo correcto, se puededecir que la lectura y analisis del fichero funcionan perfectamente, y a su vez, el metodode impresion printPOMDP, que sirvio para esta comprobacion.

Prueba 1: SUMAComprueba que las sumas de arboles se realizan correctamente. Se prueban los siguientesmetodos:

DD add(DD dd1 , DD dd2);DD addN(std :: vector <DD > ddArray );DD addN(DD dd);

Esta prueba se usa tambien para hacer comprobaciones de tiempos de calculo entre Java yC++, en el Apendice B podemos ver exactamente como se realizan estas comprobaciones.En el capıtulo 4 se exponen los resultados de estas comparaciones.

Prueba 2: RESTA Y VALOR ABSOLUTOPrueba los metodos relativos a la resta de arboles ası como el calculo del valor absolutode un arbol.

DD sub(DD dd1 , DD dd2);DD neg(DD dd);DD abs(DD dd);

Prueba 3: PRIMAR Y PERMUTARSe realizan las operaciones de primado de arboles y permutacion de sus variables. Con estaprueba comprobamos el funcionamiento de los metodos siguientes:

DD primeVars (DD dd , int n);std :: vector <DD > primeVarsN (std :: vector <DD > dds , int n);std :: vector <DD > swapVars (std :: vector <DD > ddArray , Matrix varMapping

);std :: vector <DD > swapVars (std :: vector <DD > ddArray , Matrix varMapping

);

3.1 Pruebas funcionales 41

Prueba 4: MULTIPLICACION Y DIVISIONEn esta prueba se realizan las operaciones de multiplicacion, division e inversion de arboles.Los metodos involucrados son:

DD mult(DD dd1 , DD dd2);DD multN (std :: vector <DD > ddArray );DD multN (DD dd);DD div(DD dd1 , DD dd2);DD inv(DD dd);

Prueba 5: MAXIMO Y MINIMOSe realizan los calculos de arboles maximos y mınimos. Se prueban las siguientes opera-ciones de la clase OP:

DD max(DD dd1 , DD dd2);DD maxN(std :: vector <DD > ddArray );DD maxN(DD dd);DD min(DD dd1 , DD dd2);DD min(DD dd1 , DD dd2 , Matrix config );DD threshold (DD dd , double val , int parity );bool maxNormDiff (DD dd1 , DD dd2 , double threshold )

Prueba 6: ELIMINAR VARIABLES Y UMBRALIZACIONRealiza la eliminacion de variables de varios arboles con los diferentes metodos definidospara ello, tambien realiza la operacion de umbralizacion. Se usan los siguientes metodos:

DD addMultVarElim (std :: vecto <DD > dds , Set vars);DD addMultVarElim (DD dd , Set vars);DD addMultVarElim (std :: vector <DD > dds , int var);DD addMultVarElim (DD dd , int var);DD addMultCutSet (std :: vector <DD > dds , DD dd , Set vars);DD maxAddVarElim (std :: vector <DD > dds , Set vars);DD maxAddVarElim (DD dd , Set vars);DD minAddVarElim (std :: vector <DD > dds , Set vars);DD minAddVarElim (DD dd , Set vars);DD addout (DD dd , int var);DD maxout (DD dd , int var);DD minout (DD dd , int var);int selectVarGreedily (std :: vector <DD > ddArray , Set vars);

En este caso, cuando estabamos probando las operaciones maxout y minout, necesitamosun paso mas de lo normal. Estas dos operaciones anaden al arbol resultado una confi-guracion determinada dependiendo de la variable eliminada. Cuando leemos los arbolesresultado del fichero de pruebas dado por la librerıa en Java, estos no tienen configuracionninguna, los estamos leyendo y creando de cero, por lo que su configuracion esta vacıa.Cuando comparamos ası el resultado de la operacion y el arbol leıdo, la prueba nos saleerronea, ya que, efectivamente, los dos valores que estamos comparando son diferentes. Pa-ra arreglar esto, aplicamos la operacion clearConfig sobre el resultado de maxout y minoutpara comprobar que, realmente, sı eran iguales a los arboles leıdos.


Prueba 7: RESTRINGIR Y EVALUAREjecuta las operaciones de restriccion de arboles a ciertas configuraciones, y evaluacion delos mismos para configuraciones concretas. Se prueban los siguientes metodos:

DD restrict (DD dd , Matrix config );DD restrictOrdered (DD dd , Matrix config );std :: vector <DD > restrictOrderedN (std :: vector <DD > dds , Matrix

config );std :: vector <DD > restrictOrderedN (DD dd , Matrix config );std :: vector <DD > restrictN (std :: vector <DD > dds , Matrix config );std :: vector <DD > restrictN (DD dd , Matrix config );double eval (DD dd , Matrix config );std :: vector <DD > evalN(DD dd , Matrix config );std :: vector <DD > evalN(std :: vector <DD > dds , Matrix config );

Prueba 8: PROPIEDADES DEL ARBOLSe ejecutan las operaciones que devuelven las diferentes propiedades de varios arboles.Estas son:

DD findLeaf (DD dd , DD leaf);std :: vector <double > enumerateLeaves (DD dd);int nEdges (DD dd);int nLeaves (DD dd);int nNodes (DD dd);DD extractConfig (DD dd , Set vars);DD clearConfig (DD dd);

Para probar la operacion clearConfig necesitabamos un arbol que tuviese configuracion.Como los arboles que recien se leen del fichero vienen con configuracion vacıa en sus hojas,nos apoyamos en la operacion maxout, que anade configuracion a las hojas, para realmentecomprobar que esta operacion elimina la configuracion de las hojas del arbol.

Prueba 9: PRODUCTO ESCALARCon esta prueba se comprueba el correcto funcionamiento de los diferentes metodos decalculo del producto escalar de arboles. Se usan los siguientes metodos:

std :: vector <std :: vector <double > > dotProduct (std :: vector <DD >dd1Array , std :: vector <DD > dd2Array , Set vars);

std :: vector <double > dotProduct (DD dd1 , std :: vector <DD > dd2Array ,Set vars);

std :: vector <double > dotProduct (std :: vector <DD > dd1Array , DD dd2 ,Set vars);

double dotProduct (DD dd1 , DD dd2 , Set vars);std :: vector <std :: vector <double > > dotProductLeafPrune (std :: vector <

DD > dd1Array , std :: vector <DD > dd2Array , Set vars);std :: vector <double > dotProductLeafPrune (DD dd1 , std :: vector <DD >

dd2Array , Set vars);std :: vector <double > dotProductLeafPrune (std :: vector <DD > dd1Array ,

DD dd2 , Set vars);double dotProductLeafPrune (DD dd1 , DD dd2 , std :: vector <int > vars);

3.1 Pruebas funcionales 43

std :: vector <std :: vector <double > > dotProductNoMem (std :: vector <DD >dd1Array , std :: vector <DD > dd2Array , Set vars);

double dotProductNoMem (DD dd1 , DD dd2 , Set vars);std :: vector <double > dotProductNoMem (DD dd1 , std :: vector <DD >

dd2Array , Set vars);std :: vector <double > dotProductNoMem (std :: vector <DD > dd1Array , DD

dd2 , Set vars);

Prueba 10: VALOR ESPERADOEjecutamos las diferentes versiones de las operaciones que calculan el valor esperado deuno o varios arboles. Estas operaciones son las siguientes:

double factoredExpectationSparse (std :: vector <DD >& factDist , DD dd);std :: vector < std :: vector <double > > factoredExpectationSparse (std ::

vector <std :: vector <DD > >& factDist , std :: vector <DD > ddArray );std :: vector <double > factoredExpectationSparse (std :: vector <std ::

vector <DD > >& factDist , DD dd);std :: vector <std :: vector <double > > factoredExpectationSparseNoMem (

std :: vector <std :: vector <DD > >& factDist , std :: vector <DD >ddArray );

std :: vector <double > factoredExpectationSparseNoMem (std :: vector <DD >&factDist , std :: vector <DD > ddArray );

std :: vector <double > factoredExpectationSparseNoMem (std :: vector <std:: vector <DD > >& factDist , DD dd);

double factoredExpectationSparseNoMem (std :: vector <DD >& factDist , DDdd);

std :: vector <std :: vector <double > > factoredExpectationSparseParallel(std :: vector <std :: vector <DD > >& factDist , std :: vector <DD >ddArray );

std :: vector <double > factoredExpectationSparseParallel (std :: vector <std :: vector <DD > >& factDist , DD dd);

std :: vector <std :: vector <double > >factoredExpectationSparseParallel2 (std :: vector <std :: vector <DD >>& factDist , std :: vector <DD > ddArray );

std :: vector <double > factoredExpectationSparseParallel2 (std :: vector <std :: vector <DD > >& factDist , DD dd);

std :: vector <double > factoredExpectationParallel (std :: vector <std ::vector <DD > >& factDist , DD dd);

Prueba 11: MUESTRAS ALEATORIASEsta prueba calcula muestras aleatorias de arboles a partir de las operaciones existentespara ello, que son:

int sampleMultinomial (std :: vector <double > pdist);Matrix sampleMultinomial (std :: vector <DD > ddArray , Set varSet );Matrix sampleMultinomial (DD dd , Set varSet );Matrix sampleMultinomial (DD dd , int varId);

Esta prueba es algo particular. Ya que lo que calcula son muestras aleatorias, no podıamos,como en el resto de casos, comparar los resultados con los valores dados del resultado de


la misma operacion en la librerıa en Java. Para poder probar esta operacion la ejecutamosvarias veces e imprimimos sus resultados, viendo que, efectivamente, devolvıa diferentesvalores posibles para el arbol y las variables introducidas.

Prueba 12: ORDENACION Y APROXIMACIONSe comprueba el correcto funcionamiento de las operaciones de ordenacion y aproximacionde arboles. Estas son:

DD replace (DD dd , double val1 , double val2);DD orderLast (DD dd , int varId);DD reorder (DD dd);DD approximateAll (DD dd , double tolerance );DD approximate (DD dd , double tolerance );DD approximate (DD dd , double tolerance , double prescribedLeafVal );DD approximate (DD dd , double tolerance , std :: vector <double >

prescribedLeafValues );

Prueba 13: OTRASEn esta prueba se ejecutan todas las operaciones de la clase OP restantes, es decir, lasque no estan incluidas en ninguna de las pruebas anteriores. Se incluyen las siguientesoperaciones:

std :: vector <double > sub (std :: vector <double > t1 , std :: vector <double> t2);

double max (std :: vector <double > t);double max (std :: vector <double > t, int len);double maxabs (std :: vector <double > t);std :: vector <double > maxAllN (std :: vector <DD > dds);double maxAllN (DD dd);std :: vector <double > minAllN (std :: vector <DD > dds);double minAllN (DD dd);std :: vector <std :: vector <doube > > convert2array (std :: vector <DD >

ddArray , Set varList )std :: vector <double > convert2array (DD dd , Set varList )std :: vector <double > convert2array (DD dd)

Tras ejecutar todas las pruebas se comprueba que el tiempo de lectura y analisis de losficheros que realiza esta librerıa es del orden de 10 veces mayor que el de la librerıa en Java.

3.2. Simulacion

En este apartado, simularemos un proceso basado en un POMDP, en el que un robot vamoviendose en un escenario para serguir a un objetivo movil (target). El modelo se carga conla librerıa y se simula en varios tiempos de muestreo, introduciendo a mano las lecturas de lossensores del robot ası como sus acciones, y viendo como evoluciona el belief del robot sobre elestado. El problema que vamos a simular tiene los siguientes parametros:

3.2 Simulacion 45

Variables de estado: tar0 1, posicion del target, isFound 0, indica si el target ha sidoencontrado o no, y rob0 1, posicion del robot. Se asume que el target puede moverse encada instante de tiempo a cualquiera de las casillas adyacentes. La variable isFound 0 sepone a yes cuando el robot se encuentra en la misma posicion que el target. Una vez puestaa yes, tiene una cierta probabilidad de volver a no en cada instante de tiempo, para queel robot olvide tras cierto tiempo que ha encontrado al target.

Variables de observacion: rob0 1Obs, posicion del robot observada por el mismo, cam 0Tar 0,indica si el sensor ve o no al target. Se asume que el robot puede observar su posicion contotal certeza, mientras que puede detectar al target con cierta probabilidad siempre queeste en alguna de las casillas adyacentes al robot.

Acciones: joint 0, permacer en la posicion actual, joint 1, moverse al norte, joint 2,moverse al oeste, joint 3, moverse al sur, y joint 4, moverse al este. Las acciones no sontotalmente deterministas, se modela una pequena probabilidad de error a la hora de queel robot ejecute las acciones.

Los valores de posiciones posibles, tanto para el robot como para el target, seran los que se venen la figura 3.1.

Figura 3.1: Cuadrıcula de posiciones

Ejecutaremos la simulacion durante varios pasos. Lo primero que vemos al ejecutar es losiguiente:

Figura 3.2: Belief inicial sobre el estado para la simulacion. Paso 1/5

Lo que se ve en la figura 3.2 es la representacion del belief inicial del problema. Esto nosda informacion sobre las variables de estado, en concreto la probabilidad para cada valor de


la variable. Por tanto, para tar0 1 leemos que todas los valores tienen la misma probabilidad,0.0344828, o lo que es lo mismo, no sabemos donde se encuentra el target inicialmente; is-Found 0 vale no con probabilidad 1; y para rob0 1 tenemos la misma informacion que paratar0 1, no sabemos donde se encuentra el robot inicialmente. Ahora vamos a ir indicando accio-nes manualmente e indicando los valores de las variables de observacion que nos vayan pareciendoconvenientes (siempre con sentido, no podemos indicar una accion para ir al norte y observarque nos encontramos cinco posiciones al este de lo que estabamos en el instante anterior).

Figura 3.3: Belief sobre el estado para la simulacion. Paso 2/5

Indicamos al robot que se mueva al sur, observando que se encuentra ahora en la posicionl1 5 (por lo que estamos suponiendo que en el instante inicial se encontraba en la posicion l0 5)y que no observamos al target. Veamos como evoluciona el belief sobre el espacio de estados.

Vemos en la figura 3.4 que las probabilidades de que el target se encuentre en las posicionescontiguas a l1 5, que es la posicion en la que estamos, es menor que en el resto de la cuadrıcula,y que, casi con seguridad, no lo hemos encontrado, ya que no lo vemos. Ahora nos moveremoshacia el este y supondremos que la lectura de nuestro sensor es que sı observa al target.

Vemos ahora (figura 3.5) que las unicas posiciones que pueden contener al target son lascontiguas a l1 6 y que las que tambien son contiguas a l1 5 y l0 5 son las menos probables dentrode las probables, ya que en los pasos anteriores las lecturas fueron negativas. Aun obteniendouna lectura positiva del sensor, la variable isFound 0 nos indica que aun no hemos encontradoal target, vamos a suponer que sı que lo hemos encontrado y que el target se encuentra en laposicion l1 6, por lo que permanecemos en la misma posicion varios instantes.

Tras dos instantes de tiempo en la misma posicion con lectura positiva del sensor, es decirobservando el target, el belief queda tal y como se ve en la (figura 3.6).

Vemos que la probabilidad de haber encontrado el target es ahora mayor, y que la posicioncon mas probabilidad de contenerlo es la l1 6. Si permanecemos en dicha posicion indicandoque vemos el target durante mas tiempo, estas probabilidades irıan aumentando cada vez mas.

Esta simulacion nos sirve para comprobar que las operaciones realizadas por la librerıa tienensentido una vez usadas sobre un problema POMDP real.

3.2 Simulacion 47


3.2 Simulacion 49


Capıtulo 4Conclusiones

En conclusion, podemos decir que se ha conseguido la funcionalidad buscada, es decir, unalibrerıa capaz de operar con arboles de decision de cara a usarse para crear resolvedores deproblemas de decision de Markov parcialmente obsevables.

La principal diferencia es que esta librerıa es mas lenta en ejecucion que su version en Java.A continuacion se intentara hacer un analisis de las principales diferencias identificadas entreambas versiones para posibilitar una futura optimizacion de tiempo.

LecturaLa lectura de los ficheros de entrada, ficheros con la definicion del problema, arboles, ac-ciones, belief inicial, etc, en esta librerıa se realiza de una forma muy diferente a la lecturaque se hace en su version en Java. Mientras que en Java la lectura se hace mediante unStreamTokenizer que lee directamente del fichero de entrada token a token, en C++ necesi-tamos un preprocesamiento. StreamTokenizer (java.io) ignora los comentarios del fichero,tanto en estilo C como en estilo C++, y no tiene problemas de identificacion de tokensaunque no haya espacio entre ellos, esto es, lo siguiente, palabra), lo identifica como dostokens diferentes, uno palabra y el otro ). Para simular este comportamiento en C++,tenemos una lectura y almacenamiento en un buffer (string de caracteres) del fichero taly como viene. Tras esto se relee este buffer para eliminar los comentarios y acto seguidose anaden espacios entre los elementos que queremos considerar tokens diferentes, esto es,antes y despues de parentesis y corchetes. Es sobre este resultado sobre el que leemos tokena token con un iterador sobre un tokenizer (librerıas Boost). Todo este preprocesamientoconsume un tiempo de ejecucion que en Java no consumıamos y el almacenamiento enejecucion de los bufferes necesarios consumen tambien una cantidad de memoria que noconsumimos en la version en Java, aun ası midiendo el tiempo de preprocesado se com-prueba que este consume la decima parte del tiempo de lectura completo, por lo que seconcluye que la principal diferencia esta en como trabajan internamente las librerıas queutilizamos para leer y no necesariamente en el preprocesado.

51

52 CAPITULO 4. CONCLUSIONES

Busqueda en mapas de resultadoOtro aspecto importante es la busqueda en los CacheMaps que almacenan los resultadosde las operaciones. Se ha realizado un analisis sobre la operacion de suma del que se hasacado la siguiente conclusion, la busqueda en addHashTable (ver 2.6) es unas cinco vecesmas lenta que en la version en Java. Para llegar a esta conclusion se ha medido el tiempoque se tarda, tanto en Java como en C++, en hacer una busqueda en addHashTable conlos codigos siguientes:

LARGE_INTEGER t_ini , t_fin;double secs;QueryPerformanceCounter (& t_ini);std :: unordered_map <Pair , DD >:: const_iterator storedResult = Global ::

addHashtable .umap.find(pair);QueryPerformanceCounter (& t_fin);LARGE_INTEGER freq;QueryPerformanceFrequency (& freq);secs = ( double )(t_fin. QuadPart - t_ini. QuadPart ) / ( double )freq.

QuadPart ;std :: cout << " Tiempo busqueda : " ;printf (" %.16g milliseconds \n", secs * 1000.0) ;

Listado 4.1: Calculo tiempo busqueda C++

long timesuma = System . currentTimeMillis ();DD storedResult = (DD) Global . addHashtable .get(pair);if ( storedResult != null){long t = System . currentTimeMillis () - timesuma ;System .out. println (" Tiempo busqueda :");System .out. println (t);return storedResult ;}

Listado 4.2: Calculo tiempo busqueda Java

De este analisis, se concluyo que la busqueda en unordered map, al menos en este caso, esmas lenta que la busqueda en los LinkedHashMaps de Java, por tanto, todas las operacionesque usan estos mapas para almacenar resultados y no rehacerlos son mas lentas que susversiones en Java. Una manera de estudiar esta diferencia de tiempos mas general, serıahacer una medida de todas las busqueda en los mapas para una operacion concreta ycalcular luego la media, para compararlo con el tiempo medio de busqueda en Java. En elApendice B se incluye el codigo para realizar la prueba de suma con todos los calculosnecesarios para el analisis de los tiempos.

Otra diferencia importante respecto a los CacheMaps es la generacion de los codigos hashde los tipos creados en la librerıa. Mientras que en Java esta generacion de los codigosse hace mediante la llamada al metodo de Object hashcode(), en C++ hemos necesitadosobreescribir las estructuras/clases hash de STL creando nosotros nuestro propio codigo

53

hash, por tanto, probablemente los hash creados por nosotros seran menos eficientes quelos internos de Java, lo que tambien puede ralentizar las busquedas al existir mas colisiones.

Generacion de numeros aleatoriosEn el metodo OP::sampleMultinomial se generan numeros aleatorios para poder dar mues-tras aleatorias de un arbol completo. Esta generacion de numeros aleatorios se realiza enJava con la clase Random mientras que en C++ se utiliza la librerıa random, con lasoperaciones rand() y srand(), usando como semilla time(), como la precision de time() enWindows es de unos 10 ms, en la librerıa en C++ se ha anadido un contador a la claseOP, que se incrementa cada vez que se entra en el metodo sampleMultinomial y se sumaal resultado de time() para asegurarnos ası de que siempre se modifique la semilla y portanto obtengamos una mejor aleatoriedad.

Se deja como tarea futura encontrar la manera de optimizar estos tiempos hasta que seantan buenos o mejores que los de su version en Java.

54 CAPITULO 4. CONCLUSIONES

Apendice AAspectos tecnicos

Se definen en este anexo las herramientas de compilacion necesarias para compilar estalibrerıa, ası como las librerıas necesarias.

Compilador: GCC 4.8.1

Librerıas: Boost 1.56.0

A continuacion, se muestra un ejemplo del archivo makefile necesario para la compilacion.

# Project : ParseSPUDD

CPP = g++OBJ = Config .o DD.o Global .o MySet.o Pair.o TripletConfig .o TripletSet .o

ParseSPUDD .o main.o OP.o DDcollection .oLINKOBJ = Config .o DD.o Global .o MySet.o Pair.o TripletConfig .o TripletSet .o

ParseSPUDD .o main.o OP.o DDcollection .oLIBS = -static - libgcc -pgCXXFLAGS = -std=gnu ++11 -g -O2 -pgRM = rm -f

.PHONY: all all - before all -after clean clean - custom

all: all - before $(BIN) all -after

clean: clean - custom${RM} $(OBJ2) $(BIN)

$(BIN): $(OBJ)$(CPP) $( LINKOBJ ) -o $(BIN) $(LIBS)

$(BIN2): $(OBJ2)$(CPP) $( LINKOBJ2 ) -o $(BIN2) $(LIBS)

55

56 APENDICE A. ASPECTOS TECNICOS

Config .o: Config .cpp MySet.o Types.hpp Config .hpp Global .o Pair.oTripletConfig .o CacheMap .hpp OP.o

$(CPP) -c Config .cpp -o Config .o $( CXXFLAGS )

DD.o: DD.cpp DD.hpp Types.hpp Global .o Config .o MySet.o$(CPP) -c DD.cpp -o DD.o $( CXXFLAGS )

DDcollection .o: DDcollection .cpp DDcollection .hpp DD.o$(CPP) -c DDcollection .cpp -o DDcollection .o $( CXXFLAGS )

Global .o: Global .cpp Global .hpp Types.hpp DD.hpp Pair.o TripletConfig .oCacheMap .hpp TripletSet .o

$(CPP) -c Global .cpp -o Global .o $( CXXFLAGS )

MySet.o: MySet.cpp MySet.hpp Types.hpp$(CPP) -c MySet.cpp -o MySet.o $( CXXFLAGS )

Pair.o: Pair.cpp Pair.hpp DD.o Types.hpp$(CPP) -c Pair.cpp -o Pair.o $( CXXFLAGS )

TripletConfig .o: TripletConfig .cpp TripletConfig .hpp DD.o Types.hpp Config .hpp

$(CPP) -c TripletConfig .cpp -o TripletConfig .o $( CXXFLAGS )

TripletSet .o: TripletSet .cpp TripletSet .hpp DD.o Types.hpp MySet.o$(CPP) -c TripletSet .cpp -o TripletSet .o $( CXXFLAGS )

ParseSPUDD .o: ParseSPUDD .cpp ParseSPUDD .hpp DD.o Types.hpp Global .o Pair.oTripletConfig .o CacheMap .hpp OP.o

$(CPP) -c ParseSPUDD .cpp -o ParseSPUDD .o $( CXXFLAGS )

main.o: main.cpp ParseSPUDD .o DD.o Types.hpp$(CPP) -c main.cpp -o main.o $( CXXFLAGS )

OP.o: OP.hpp OP.cpp Global .o Pair.o TripletConfig .o Config .hpp DD.o Types.hppMySet.o

$(CPP) -c OP.cpp -o OP.o $( CXXFLAGS )

Listado A.1: Makefile

Apendice BPrueba de suma y calculos de tiempo

Primeramente vemos como hacer la suma y compararla con la suma realizada en Java, paraver si ambas operaciones dan el mismo resultado. El archivo Pruebas suma.txt debe contener ladefinicion de las variables de los arboles implicados ası como la definicion de estos arboles, y elresultado de su suma.

//# include <windows .h> libreria para el calculo de tiempos SOLO PARA WIDOWS# include <sys/time.h>

(...)

ParseSPUDD psuma (( char *) " Pruebas_suma .txt");psuma. parsePOMDP ( false );std :: ofstream fsuma;fsuma.open(" Pruebas .txt", std :: ofstream :: out | std :: ofstream :: app);fsuma << " Prueba 1.1: SUMA lObs_0 + dcam_0Tar_0 \n";DD dd1 = psuma . existingDds [" lObs_0 "];DD dd2 = psuma . existingDds [" dcam_0Tar_0 "];/** Calculo de tiempo de ejecucion de la suma. SOLO PARA WINDOWS*//* LARGE_INTEGER t_ini , t_fin;double secs;QueryPerformanceCounter (& t_ini);DD dds = OP:: add(dd1 , dd2);QueryPerformanceCounter (& t_fin);LARGE_INTEGER freq;QueryPerformanceFrequency (& freq);secs = ( double ) (t_fin. QuadPart - t_ini. QuadPart ) / ( double ) freq. QuadPart ;std :: cout << " Tiempo suma: ";printf (" %.16g milliseconds \n", secs * 1000.0) ;*//** Calculo de tiempo de ejecucion de la suma. LINUX*/struct timeval iniTime , endTime ;

57

58 APENDICE B. PRUEBA DE SUMA Y CALCULOS DE TIEMPO

gettimeofday (& iniTime , NULL);DD dds = OP:: add(dd1 , dd2);gettimeofday (& endTime , NULL);double timeval_diff = ( double ) ( endTime . tv_sec + ( double ) endTime . tv_usec /

1000000) - ( double ) ( iniTime . tv_sec + ( double ) iniTime . tv_usec / 1000000);

std :: cout << " Tiempo suma: ";printf (" %.16g segundos \n", timeval_diff );DD ddsumaj = psuma. existingDds [" Padd_dd "];if ( ddsumaj == dds)

fsuma << "OK\n";else

fsuma << "ERROR\n";fsuma.close ();

Listado B.1: Prueba de suma y calculos de tiempo

En el codigo anterior vemos como realizar el calculo del tiempo completo de la operacion.Para realizar los calculos de las busquedas en los mapas debemos irnos a la operacion add en laclase OP.

DD OP:: add(DD dd1 , DD dd2) {

if (dd1. getVar () > dd2. getVar ()) {

if (dd2. getVar () == 0 && dd2. getVal () == 0 && dd2. getConfig ().empty ()) {

return dd1;}Pair pair(dd1 , dd2);/** Calculo de tiempo de busqueda en el mapa. SOLO PARA WINDOWS*//* LARGE_INTEGER t_ini , t_fin;double secs;QueryPerformanceCounter (& t_ini);

std :: unordered_map <Pair , DD >:: const_iterator storedResult =Global :: addHashtable .umap.find(pair);

QueryPerformanceCounter (& t_fin);LARGE_INTEGER freq;QueryPerformanceFrequency (& freq);secs = ( double )(t_fin. QuadPart - t_ini. QuadPart ) / ( double )

freq. QuadPart ;std :: cout << " Tiempo busqueda : " ;printf (" %.16g milliseconds \n", secs * 1000.0) ;*//** Calculo de tiempo de busqueda en el mapa. LINUX*/

59

struct timeval iniTime , endTime ;gettimeofday (& iniTime , NULL);


gettimeofday (& endTime , NULL);double timeval_diff = ( double ) ( endTime . tv_sec + ( double )

endTime . tv_usec / 1000000) - ( double ) ( iniTime . tv_sec + (double ) iniTime . tv_usec / 1000000) ;

std :: cout << " Tiempo busqueda : ";printf (" %.16g segundos \n", timeval_diff );

if ( storedResult != Global :: addHashtable .umap.end ()) {return ((* storedResult ). second );

}std :: vector <DD > children (dd1. getChildren ().size ());for (int i = 0; i < (int) dd1. getChildren ().size (); i++) {

children [i] = OP:: add(dd1. getChildren ()[i], dd2);}DD result = DD:: myNew(dd1. getVar (), children );

return result ;}// dd2 precede a dd1

else if (dd2. getVar () > dd1. getVar ()) {

if (dd1. getVar () == 0 && dd1. getVal () == 0 && dd1. getConfig ().empty ())

return dd2;

Pair pair(dd1 , dd2);/** Calculo de tiempo de busqueda en el mapa. SOLO PARA WINDOWS*//* LARGE_INTEGER t_ini , t_fin;double secs;QueryPerformanceCounter (& t_ini);



freq. QuadPart ;std :: cout << " Tiempo busqueda : " ;printf (" %.16g milliseconds \n", secs * 1000.0) ;*//** Calculo de tiempo de busqueda en el mapa. LINUX*/


struct timeval iniTime , endTime ;gettimeofday (& iniTime , NULL);




std :: cout << " Tiempo busqueda : ";printf (" %.16g segundos \n", timeval_diff );

if ( storedResult != Global :: addHashtable .umap.end ()) {return ((* storedResult ). second );

}

std :: vector <DD > children (dd2. getChildren ().size ());for ( unsigned int i = 0; i < dd2. getChildren ().size (); i++) {

children [i] = OP:: add(dd2. getChildren ()[i], dd1);}DD result = DD:: myNew(dd2. getVar (), children );Global :: addHashtable .put(pair , result );return result ;}// dd2 y dd1 tienen la misma variable raiz

else if (dd1. getVar () > 0) {

Pair pair(dd1 , dd2);/** Calculo de tiempo de busqueda en el mapa. SOLO PARA WINDOWS*//* LARGE_INTEGER t_ini , t_fin;double secs;QueryPerformanceCounter (& t_ini);



freq. QuadPart ;std :: cout << " Tiempo busqueda : " ;printf (" %.16g milliseconds \n", secs * 1000.0) ;*//** Calculo de tiempo de busqueda en el mapa. LINUX*/struct timeval iniTime , endTime ;gettimeofday (& iniTime , NULL);

61




std :: cout << " Tiempo busqueda : ";printf (" %.16g segundos \n", timeval_diff );if ( storedResult != Global :: addHashtable .umap.end ()) {

return ((* storedResult ). second );}

std :: vector <DD > children (dd1. getChildren ().size ());for ( unsigned int i = 0; i < dd1. getChildren ().size (); i++) {

children [i] = OP:: add(dd1. getChildren ()[i], dd2.getChildren ()[i]);

}DD result = DD:: myNew(dd1. getVar (), children );Global :: addHashtable .put(pair , result );return result ;}// dd1 y dd2 son hojas

else {double newVal = dd1. getVal () + dd2. getVal ();Matrix newConfig = Config :: merge(dd1. getConfig (), dd2.

getConfig ());DD ddr = DD:: myNew(newVal , newConfig );return ddr;

}}

Listado B.2: Calculos de tiempo en OP::add

Con los resultados de estos calculos tras una operacion podemos calcular la media de tiempode acceso a los mapas en C++. La realizacion de estos mismos calculos en Java serıan comosigue:

PrintStream wsuma = new PrintStream (new FileOutputStream (new File("Arbol/Pruebas_suma .txt")));

wsuma. println ("// Prueba 1: SUMA\n\n");imprimevariables (wsuma , file);DD dd1s = (DD)file. existingDds .get(" lObs_0 ");wsuma. println ("dd lObs_0 ");dd1s. printSpuddDD (wsuma);wsuma. println ("enddd\n\n");DD dd2s = (DD)file. existingDds .get(" dcam_0Tar_0 ");wsuma. println ("dd dcam_0Tar_0 ");dd2s. printSpuddDD (wsuma);wsuma. println ("enddd\n\n");// Calculo del tiempo de ejecucion de una suma


long timesuma = System . currentTimeMillis ();DD ddadd = OP.add(dd1s , dd2s);System .out. println (" Tiempo suma:");System .out. println ( System . currentTimeMillis ()-timesuma );wsuma. println ("dd Padd_dd ");ddadd. printSpuddDD (wsuma);wsuma. println ("enddd\n\n");wsuma.close ();

Listado B.3: Prueba de suma y calculos de tiempo en Java

public static DD add(DD dd1 , DD dd2) {// dd1 precedes dd2

if (dd1. getVar () > dd2. getVar ()) {

if (dd2. getVar () == 0 && dd2. getVal () == 0 && dd2. getConfig ()== null)

return dd1;

Pair pair = new Pair(dd1 , dd2);// Calculo del tiempo de busqueda en el mapalong timesuma = System . currentTimeMillis ();DD storedResult = (DD) Global . addHashtable .get(pair);long t = System . currentTimeMillis ()-timesuma ;System .out. println (" Tiempo busqueda :");System .out. println (t);if ( storedResult != null){

return storedResult ;}

DD children [];children = new DD[dd1. getChildren (). length ];for (int i = 0; i < dd1. getChildren (). length ; i++) {

children [i] = OP.add(dd1. getChildren ()[i], dd2);}DD result = DDnode .myNew(dd1. getVar (), children );Global . addHashtable .put(pair , result );return result ;

}

// dd2 precedes dd1 {else if (dd2. getVar () > dd1. getVar ()) {

if (dd1. getVar () == 0 && dd1. getVal () == 0 && dd1. getConfig ()== null)

return dd2;

Pair pair = new Pair(dd1 , dd2);// Calculo del tiempo de busqueda en el mapalong timesuma = System . currentTimeMillis ();

63

DD storedResult = (DD) Global . addHashtable .get(pair);long t = System . currentTimeMillis ()-timesuma ;System .out. println (" Tiempo busqueda :");System .out. println (t);if ( storedResult != null){



children [i] = OP.add(dd2. getChildren ()[i], dd1);}DD result = DDnode .myNew(dd2. getVar (), children );Global . addHashtable .put(pair , result );return result ;

}

// dd2 and dd1 have same root varelse if (dd1. getVar () > 0) {

Pair pair = new Pair(dd1 , dd2);// Calculo del tiempo de busqueda en el mapalong timesuma = System . currentTimeMillis ();DD storedResult = (DD) Global . addHashtable .get(pair);long t = System . currentTimeMillis ()-timesuma ;System .out. println (" Tiempo busqueda :");System .out. println (t);if ( storedResult != null){



children [i] = OP.add(dd1. getChildren ()[i], dd2.getChildren ()[i]);

}DD result = DDnode .myNew(dd1. getVar (), children );Global . addHashtable .put(pair , result );return result ;

}

// dd1 and dd2 are leaveselse {

double newVal = dd1. getVal () + dd2. getVal ();int [][] newConfig = Config .merge(dd1. getConfig (), dd2.

getConfig ());return DDleaf .myNew(newVal , newConfig );

}


}

Listado B.4: Calculos de tiempo en OP.add

Bibliografıa

[1] C. de Wikipedia, “Propiedad de Markov.” [Online]. Available: http://es.wikipedia.org/w/index.php?title=Propiedad de M%C3%A1rkov&oldid=73933272

[2] M. Delgado, “Procesos de decision markovianos.” [Online]. Available: http://www.slideshare.net/MairaDelgado/procesos-de-decisionmarkovianos1

[3] C. de Wikipedia, “Markov Decision Process.” [Online]. Available: http://en.wikipedia.org/w/index.php?title=Markov decision process&oldid=615180994

[4] A. R. Ballesteros, “Representacion y aprendizaje de procesos de decision de Markov cuali-tativos.” [Online]. Available: http://campus.cva.itesm.mx/areyes/reportes/tesisARB.pdf

[5] C. de Wikipedia, “Partially observable Markov decision process.” [Online]. Avai-lable: http://en.wikipedia.org/w/index.php?title=Partially observable Markov decisionprocess&oldid=608850038

[6] J. C. Fernandez, “Cooperacion descentralizada para percepcion activa con multiples robots.”[Online]. Available: http://fondosdigitales.us.es/media/thesis/1521/D T.PROV18.pdf

[7] “Hash Functions.” [Online]. Available: http://anh.cs.luc.edu/331/notes/hash.pdf

65

http://es.wikipedia.org/w/index.php?title=Propiedad_de_M%C3%A1rkov&oldid=73933272

http://es.wikipedia.org/w/index.php?title=Propiedad_de_M%C3%A1rkov&oldid=73933272

http://www.slideshare.net/MairaDelgado/procesos-de-decisionmarkovianos1

http://www.slideshare.net/MairaDelgado/procesos-de-decisionmarkovianos1

http://en.wikipedia.org/w/index.php?title=Markov_decision_process&oldid=615180994

http://en.wikipedia.org/w/index.php?title=Markov_decision_process&oldid=615180994

http://campus.cva.itesm.mx/areyes/reportes/tesisARB.pdf

http://en.wikipedia.org/w/index.php?title=Partially_observable_Markov_decision_process&oldid=608850038

http://en.wikipedia.org/w/index.php?title=Partially_observable_Markov_decision_process&oldid=608850038

http://fondosdigitales.us.es/media/thesis/1521/D_T.PROV18.pdf

http://anh.cs.luc.edu/331/notes/hash.pdf

proyecto fin de carrera ingenier´ıa de...

Documents