Personalización de rutas en sistemas de turismo y ocio

Universidad Complutense de Madrid Facultad de Informática Doble Grado en Ingeniería Informática y Matemáticas PERSONALIZACIÓN DE RUTAS EN SISTEMAS DE TURISMO Y OCIO TRABAJO DE FIN DE GRADO Jesús Aguirre Pemán Tutor: María Belén Díaz Agudo Tutor: Guillermo Jiménez Díaz 17 de junio de 2016 PERSONALIZACIÓN DE RUTAS EN SISTEMAS DE TURISMO Y OCIO Autor: Jesús Aguirre Pemán Tutor: María Belén Díaz Agudo Tutor: Guillermo Jiménez Díaz Departamento de Ingeniería del Software e Inteligencia Articial Facultad de Informática Universidad Complutense de Madrid 17 de junio de 2016 5 AUTORIZACIÓN PARA LA DIFUSIÓN DEL TRABAJO FIN DE GRADO Y SU DEPÓSITO EN EL REPOSITORIO INSTITUCIONAL E-PRINTS COMPLUTENSE Los abajo firmantes, alumno/s y tutor/es del Trabajo Fin de Grado (TFG) en el Grado en …………………………………………………………………………………………de la Facultad de …………………………………………………..………, autorizan a la Universidad Complutense de Madrid (UCM) a difundir y utilizar con fines académicos, no comerciales y mencionando expresamente a su autor el Trabajo Fin de Grado (TF) cuyos datos se detallan a continuación. Así mismo autorizan a la Universidad Complutense de Madrid a que sea depositado en acceso abierto en el repositorio institucional con el objeto de incrementar la difusión, uso e impacto del TFG en Internet y garantizar su preservación y acceso a largo plazo. Periodo de embargo (opcional):  6 meses  12meses TÍTULO del TFG: .......................................................................................................... …………………………………………………………………………………………………. Curso académico: 20….. / 20….. Nombre del Alumno/s: ………………………………………………………………………………………………… ………………………………………………………………………………………………… Tutor/es del TFG y departamento al que pertenece: ………………………………………………………………………………………………… ………………………………………………………………………………………………… ………………………………………………………………………………………………… Firma del alumno/s Firma del tutor/es Abstract Abstract  The aim of this work is to provide a general and theoretical frame to personalize routes in tourism and leisure-time domains. We will also describe techniques that use Augmented Reality to improve user experience on the recommended routes. To do this, we will introduce the necessary concepts of Graph Theory and path- nding algorithms. Afterwards, we will describe the problem of personalizing a route for individuals and groups, proposing three dierent approaches for its resolution: using A ? algorithm, greedy algorithm, and case based reasoning, respectively. We will also analize the techniques and devices in Augmented Reality. With the goal of seeing specic examples of the general frame exposed in this work, we will propose two case studies where we will apply the aforementioned personalization algorithms and Augmented Reality techniques. These case studies will be focused in the García Santesmases Museum of Computer Science and in the tourism domain in Madrid. Key words  Personalization, graph, CBR, A ? , greedy algorithms, Augmented Reality. Personalización de rutas en sistemas de turismo y ocio III Resumen Resumen  El objetivo de este trabajo es proporcionar un marco general y teórico para la personalización de rutas en sistemas de turismo y ocio. Además, se verán técnicas que utilizan Realidad Aumentada para mejorar la experiencia del usuario que recorra esas rutas. Para ello, se introducirán los conceptos necesarios de teoría de grafos, así como los algoritmos para recorrerlos. Posteriormente, describiremos el problema de personalización de rutas para individuos y grupos, proponiendo tres enfoques distintos para su resolución: utilizando el algoritmo A ? , el algoritmo voraz, y el razonamiento basado en casos respectivamente. Además, se realizará un análisis sobre Realidad Aumentada, explicando los distintos dispositivos y técnicas que se utilizan en ella. Con el objetivo de ver un ejemplo del marco general denido en este trabajo, estudiaremos dos casos en los que aplicaremos los algoritmos de personalización y técnicas de Realidad Aumentada explicadas anteriormente. Dichos casos de uso estarán centrados en el Museo de Informática García Santesmases y en el ámbito del turismo en Madrid. Palabras clave  Personalización, grafo, CBR, A ? , algoritmos voraces, Realidad Aumentada. Personalización de rutas en sistemas de turismo y ocio V CAPÍTULO 1. INTRODUCCIÓN Y OBJETIVOS 1.2. Objetivos Se pretende proponer un marco general y teórico que permita personalizar rutas en diferentes dominios. Para lograr este objetivo, deberemos completar varios objetivos intermedios. 1. Analizar las técnicas de personalización de rutas. 2. Analizar las posibilidades de la Realidad Aumentada y los diferentes entornos de la misma. 3. Proponer un modelo genérico reutilizable para diferentes casos de estudio. 4. Estudiar la adecuación de los algoritmos para encontrar la mejor ruta dado un grafo y las preferencias del usuario o del grupo. 5. Probar el modelo propuesto, aplicándolo a dos casos de estudio diferentes. 6. Realizar una comparativa experimental entre los algoritmos aplicados a los casos de estudio. 7. Aplicar técnicas de Realidad Aumentada a la representación visual de las rutas recomendadas. 8. Realizar un prototipo de aplicación móvil para cada caso de estudio que ayude al usuario a recorrer la ruta. 1.3. Organización del trabajo En primer lugar estudiaremos las bases teóricas sobre las que construir los algoritmos de personalización de rutas. Haremos un análisis de la Teoría de Grafos y de los algoritmos para recorrerlos. También se denirá el concepto de Realidad Aumentada, y se indicará cómo se puede aplicar a la recomendación de ocio y turismo para mejorar la experiencia del usuario. Veremos las diferencias entre Realidad Aumentada en exteriores y en interiores, cómo se pueden solucionar los problemas de localización en interiores y los distintos entornos de desarrollo existentes. En el Capítulo 3 propondremos un marco teórico para la recomendación de rutas personalizadas, que será adaptable a distintos casos de estudio concretos. En este capítulo formalizaremos el problema a resolver, y propondremos tres algoritmos de recomendación diferentes que permitirán utilizar búsquedas heurísticas y conocimiento experto para proporcionar las rutas personalizadas a los usuarios. Posteriormente, estudiaremos dos casos de uso donde se han aplicado las soluciones explicadas en el capítulo anterior a problemas reales. En el primero, recomendaremos visitas personalizadas al Museo de Informática García Santesmases, utilizando técnicas 2 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 1. INTRODUCCIÓN Y OBJETIVOS de Realidad Aumentada en interiores para proporcionar información adicional a los visitantes. En el segundo, proporcionaremos recomendaciones de ocio y turismo en Madrid, utilizando Realidad Aumentada en exteriores para guiar a los usuarios a los puntos de interés que formarán la ruta personalizada. Finalmente, terminaremos con unas conclusiones que resuman y valoren los resultados obtenidos a lo largo del trabajo, y expondremos las líneas de trabajo futuro que permitirían mejorar las rutas personalizadas y las experiencias de Realidad Aumentada vistas en esta memoria. Personalización de rutas en sistemas de turismo y ocio 3 2 Estado del arte En este capítulo presentaremos la base teórica sobre la que construir los algoritmos de personalización de rutas, así como las bases de Realidad Aumentada necesarias para poder aplicar sus técnicas a las rutas propuestas. Para ello, comenzaremos con una introducción sobre Teoría de Grafos que presente las deniciones necesarias para formalizar el problema. Posteriormente veremos qué son los sistemas recomendadores y en qué categorías se subdividen. Por último, introduciremos el concepto de Realidad Aumentada y veremos qué posibilidades ofrece para mejorar la experiencia del usuario durante el recorrido de la ruta. 2.1. Personalización de rutas En esta sección estudiaremos los conceptos de Teoría de Grafos necesarios para formalizar adecuadamente nuestro problema, así como una introducción teórica a los algoritmos de búsqueda heurística y a los algoritmos basados en conocimiento. Concluiremos con un análisis del trabajo relacionado con los ámbitos de ocio y turismo 2.1.1. Introducción a los grafos Para poder denir formalmente el problema que queremos abordar, necesitaremos algunas deniciones previas sobre Teoría de Grafos [2]. Denición 1. Un grafo simple (no) dirigido G= (V, E) consta de V , un conjunto no vacío de vértices o nodos , y de E , un conjunto de pares (no) ordenados de elementos distintos de V , llamados aristas . Personalización de rutas en sistemas de turismo y ocio 5 CAPÍTULO 2. ESTADO DEL ARTE Denición 2. Se dice que dos vértices u y v de un grafo no dirigido G son adyacentes en G si {u, v} es una arista de G . También se dice que la arista e conecta u y v . Denición 3. Sea n un entero no negativo y sea G un grafo no dirigido. Un camino de longitud n de u a v en G es una secuencia de n aristas a1, a2, . . . , an de G tal que f(a1) = {x0, x1}, f(a2) = {x0, x1}, . . . , f(an) = {xn−1, xn} , donde x0=u y xn=v . Se dice que el camino pasa por los vértices x1, x2, . . . , xn−1 o también que recorre las aristas a1, a2, . . . , an . Ya podemos trazar caminos en grafos. Para ver las restricciones existentes sobre esos caminos, introduzcamos ahora los conceptos de conexión en grafos. Denición 4. Se dice que un grafo no dirigido es conexo si hay un camino entre cada par de vértices distintos del grafo. Para los grafos dirigidos, la denición equivalente es la siguiente: Denición 5. Se dice que un grafo dirigido es fuertemente conexo si hay un camino de vi a vj y un camino de vj a vi para cualesquiera dos vértices vi y vj del grafo. Teorema 1. Siempre hay un camino entre cada par de vértices distintos de un grafo no dirigido conexo. Con las deniciones vistas, ya estamos en disposición de estudiar cómo recorrer los grafos mediante algoritmos de búsqueda. 2.1.2. Algoritmos de búsqueda en grafos En primer lugar, la búsqueda en el espacio de estados es un proceso por el que se consideran sucesivos estados de una instancia con el objetivo de encontrar un estado objetivo con una propiedad buscada. Esta búsqueda puede ser no informada , como las búsquedas primero en anchura y primero en profundidad. La búsqueda primero en anchura es una estrategia en la que en primer lugar se expande (calculando sus sucesores) el nodo raíz, a continuación sus sucesores, después los sucesores de estos, y así iterativamente. Por su parte, la búsqueda primero en profundidad expande el nodo al nivel más profundo en el árbol de búsqueda [3]. Se denomina búsqueda informada a la que utiliza el conocimiento especíco del problema más allá de la denición del problema en sí mismo [3]. A la aproximación general que consideraremos se le llamará búsqueda primero el mejor . La búsqueda primero el mejor es un caso particular del algoritmo general de búsqueda en grafos en el cual el nodo elegido para continuar con la búsqueda se basa en una función de evaluación f(n) . El algoritmo A ? es un algoritmo para encontrar el mejor camino en un grafo. Utiliza una función de evaluación f(n) = g(n) + h(n) , donde g calcula el coste del camino desde el nodo origen hasta el actual y h es la función heurística que estima el coste del camino desde el nodo actual hasta el nal [4]. 6 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 2. ESTADO DEL ARTE Este algoritmo combina las búsquedas primero en anchura y primero en profundidad [5]. La función h es la única componente utilizada en los algoritmos voraces, y g tiende a primero en anchura. De este modo, se cambia de camino de búsqueda cada vez que haya nodos más prometedores. Al ser un algoritmo de búsqueda en anchura, A ? es completo : en caso de existir una solución, siempre dará con ella. Para garantizar que la solución encontrada sea óptima, la función h(n) debe ser una heurística admisible , es decir, que no sobrestime el coste real de alcanzar el nodo objetivo [4]. A ? admite dos implementaciones diferentes. Nosotros utilizaremos la versión TreeSearch [6] en lugar de la Graph-Search. La diferencia entre las dos es que la Tree-Search obtiene siempre la solución óptima si la heurística elegida es admisible, mientras que para que Graph-Search llegue a la solución óptima, la heurística utilizada debe ser consistente , es decir, que para cada nodo vi y su sucesor vj se cumple h(vi)≤b(vi, vj) + h(vj) . Toda heurística consistente también es admisible, de ahí que utilicemos el paradigma TreeSearch. Podemos ver el pseudocódigo de A ? en el Algoritmo 1. Algoritmo 1: A ? según el paradigma Tree-Search Function TreeSearch(Nodo raiz) PriorityQueue frontera = sucesores( raiz ); while (|frontera|>0) do nodo = extraer( frontera ) ; // elige el nodo de mejor coste estimado estado =estadonodo ; if (objetivo( estado )) then return solucion( nodo ); end for cada sucesor de nodo do insertar( frontera , sucesor ); end end return fallo; Para poder aplicarlo a un problema, necesitaremos las siguientes deniciones: Cuál es el objetivo del problema. Cuáles son las acciones del problema. Cuál es el coste estimado de la solución. En nuestro caso, el objetivo del problema es encontrar un camino que nos permita visitar el mayor número de nodos de acuerdo con nuestros gustos. Como hemos mencionado al introducir el algoritmo A ? , el coste estimado de la solución es la función f=g+h . Las acciones del problema son añadir nodos al camino que estamos considerando como posible solución. Personalización de rutas en sistemas de turismo y ocio 7 CAPÍTULO 2. ESTADO DEL ARTE 2.1.3. Sistemas recomendadores Los sistemas recomendadores (RS, recommender systems ) son herramientas software y técnicas que proporcionan sugerencias útiles de items para los usuarios [7]. El término item es de uso general, y se utiliza para indicar el tipo de contenido que recomienda el sistema. Los sistemas recomendadores se pueden dividir en seis categorías [8]. Basado en contenido: identican las características de los items que han recibido una valoración positiva un usuario y recomiendan nuevos items que tengan características similares a aquellos. Filtrado colaborativo: consiste en realizar recomendaciones basándose en las valoraciones de los usuarios. Cubre varias de las limitaciones del enfoque basado en contenido, puesto que algún item cuyo contenido sea difícil de expresar siempre podrá ser recomendado gracias a la valoración de los usuarios. Además, el ltrado colaborativo evita posibles problemas derivados del mal etiquetado de los objetos. A su vez, los sistemas de ltrado colaborativo pueden dividirse en 2 tipos [9].  Neighborhood: las valoraciones de los usuarios se utilizan directamente para predecir las valoraciones de los nuevos items.  Basado en modelo: utilizan las valoraciones de los usuarios para aprender un modelo predictivo. Este modelo es entrenado utilizando los datos disponibles y posteriormente es utilizado para predecir nuevas valoraciones. Demográco: el sistema se basa en el perl demográco del usuario. Basado en conocimiento: la recomendación se basa en el conocimiento experto sobre cómo ciertos items satisfacen las preferencias de los usuarios. Basados en comunidad: este tipo de sistemas recomendadores se basan en las preferencias de los amigos del usuario, basándose en el hecho de que las personas confían más en las recomendaciones de sus amigos que en las de otros usuarios anónimos con gustos similares a los suyos. Híbridos: son combinación de las técnicas anteriores. 2.1.4. CBR El Razonamiento Basado en Casos (CBR, Case Based Reasoning) consiste en resolver un problema utilizando para ello una situación pasada similar, de la que reutilizamos información y conocimiento [38]. Un ciclo CBR puede ser descrito por los siguientes cuatro procesos: 1. Recuperar de la base de casos el caso más similar a una consulta realizada por un usuario. 8 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 2. ESTADO DEL ARTE 2. Reutilizar la información y conocimiento de ese caso para solucionar el problema. 3. Revisar la solución propuesta. 4. Retener las partes de la experiencia que puedan ser utilizadas para resolver futuros problemas. 2.1.5. Trabajo relacionado El problema de búsqueda de rutas en el dominio del turismo ha sido abordado usando diferentes aproximaciones. Una de las mas clásicas y conocidas es el problema del camino más corto, que no tiene en cuenta preferencias de usuario. Sistemas como MacauMap [11] mezclan otros algoritmos que incluyen intereses del usuario para seleccionar los puntos de interés de la ruta recomendada, y genera la secuencia de viaje usando un algoritmo de búsqueda A ? . Como en este trabajo, el recomendado considera el tiempo entre los puntos de interés y los tiempos de visita para proporcionar un recorrido óptimo. Los sistemas recomendadores se han utilizado de forma creciente en el campo de turismo, recomendación de atracciones o puntos de interés, serviciones de viaje (restaurantes, hoteles, transportes,...), rutas y tours, o planes personalizados de varios días, entre otros [10]. Otras aproximaciones para recomendar itinerarios de turismo son categorizadas como el Problema de Satisfacción de Restricciones: el sistema recomendador genera una secuencia de puntos de interés a visitar, ltrando datos de acuerdo a las restricciones del usuario especicadas en la consulta. Este es el enfoque empleado por INTRIGUE [12], que recomienda itinerarios y destinos teniendo en cuenta las preferencias de un grupo de personas. Varios sistemas recomendadores afrontan el problema como un problema de orientación con restricciones impuestas por los usuarios. PERSTOUR [13] recomienda rutas personalizadas utilizando la similitud entre puntos de interés y preferencias de los usuarios, inferidas de fotografías geolocalizadas. Recomienda un itinerario, con un límite de tiempo y un punto de partida y otro de salida especicados por el usuario, que maximiza la popularidad y el interés del usuario en los puntos recomendados, a la vez que se ciñe a una restricción de tiempo. Las mayores de las contribuciones de este trabajo son la personalización de la duración de la visita en cada punto, y la medición del nivel de interés del usuario en una categoría de puntos de interés basándose en el tiempo que el usuario pasa en estos puntos, relativo al usuario medio. El interés del usuario y la recomendación de puntos de interés implican la existencia de descripción de conocimiento sobre estos puntos. El sistema T-Path [14] selecciona los itinerarios que mejor encajan con las preferencias de los usuarios clasicando los puntos de interés en categorías e inriendo el vector de categorías utilizando una Red Bayesiana. Después, el sistema selecciona los itinerarios que son más similares al modelo del usuario, representado por un vector de categorías creado con la información coleccionada de las interacciones con el usuario. Personalización de rutas en sistemas de turismo y ocio 9 CAPÍTULO 2. ESTADO DEL ARTE El uso de aproximaciones CBR en la recomendación de itinerarios turísticos no es comúnmente empleado a pesar de que la planicación basada en casos es un campo que presenta resultados satisfactorios. Aunque TURAS [15] no proporciona recomendaciones de turismo, el trabajo sobresale por ser un sistema de planicación de rutas basado en casos que genera rutas personalizadas reutilizando partes relevantes de múltiples casos. Otro sistema especíco de recomendación de rutas turísticas basada en casos es TOURIST GUIDE-USAL [16], que genera la ruta adaptando casos previos al perl del usuario descrito por características como el tipo de visita, el presupuesto o la duración. En este sistema, ls casos son rutas anteriores que incluyen los puntos de interés a vista, el tiempo a pasar en cada punto, el tiempo requerido para viajar de un punto a otro y etiquetas de las rutas (como ruta de museos, ruta de familia, ruta Románica, etc). Este trabajo inspiró nuestra aproximación a la planicación de rutas usando CBR. 2.2. Realidad Aumentada La Realidad Aumentada (RA) es una técnica que permite mezclar elementos del mundo real con elementos digitales, integrando ambas partes en una sola vista [17]. Aunque sus inicios se remontan a la década de 1960, en los últimos años se ha producido una revolución en esta tecnología, motivada en gran parte por la aparición de los smartphones , que nos permiten visualizar la Realidad Aumentada sin necesidad de utilizar complejos sistemas como los dispositivos montados sobre la cabeza que se usaban en los comienzos de esta tecnología. El crecimiento de la RA ha permitido que el rango de sus aplicaciones se haya expandido notoriamente: anuncios, entretenimiento, educación, uso médico y un largo eccétera. 2.2.1. Denición La Realidad Aumentada (RA) se dene como una vista en tiempo real de un entorno real que ha sido mejorado/aumentado al añadirle información virtual generada por ordenador. El objetivo de la Realidad Aumentada es facilitar las tareas del usuario proporcionándole información [17]. Mientras que la Realidad Virtual sumerge por completo al usuario en el Entorno Virtual sin que pueda percibir el mundo real, la Realidad Aumentada aumenta el sentido de la realidad superponiendo objetos virtuales sobre el entorno real en tiempo real. En lugar de considerar la Realidad Aumentada y la Realidad Virtual como conceptos diametralmente opuestos, es conveniente verlos como los extremos de un continuo ( continuum ) [18], que podemos observar en la Figura 2.1. 10 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 2. ESTADO DEL ARTE Figura 2.1: Continuo Realidad-Virtualidad 2.2.2. Historia La primera aparición del concepto Realidad Aumentada se remonta a la década de 1950, cuando el cineasta Morton Heilig patentó el Sensorama, un simulador que proporcionaba una ilusión de realidad utilizando vídeo en 3D, olor, vibraciones en el asiento y viento, involucrando así la mayor parte de los sentidos [19]. En 1968, Ivan Sutherland creó un sistema de realidad Aumentada utilizando un dispositivo de visualización HMD (visualización montada en la cabeza), que coloca tanto las imágenes del mundo real como las del entorno virtual sobre la vista del usuario. En los años 90, la Realidad Aumentada experimentó un gran crecimiento. En 1992 se presenta el primer paper sobre un prototipo de sistema RA (llamado KARMA), y dos años más tarde, Milgram y Kishino denirían el continuo realidad-virtualidad visto anteriormente. En 1997, Ronald Azuma escribe el primer estudio sobre Realidad Aumentada, donde describe los principales campos de aplicación de estas técnicas, así como los distintos tipos de RA y su funcionamiento [20]. Este estudio se convertiría en el texto más importante sobre Realidad Aumentada hasta la actualidad. En 1999 Hirokazu Kato desarrolla ARToolKit 1 , el primer SDK de Realidad Aumentada, que posteriomente será publicado por la Universidad de Washington. Durante la década de 2000, se realizan diversos proyectos de RA con ARToolKit . En 2003 se presenta un sistema de guía en interiores utilizando RA [21]. La aplicación utiliza un dispositivo portátil y ARToolKit para proporcionar una vista aumentada del entorno. En 2006, Reitmayr y Drummond presentan un sistema de tracking para RA en exteriores, utilizando un dispositivo portátil [22]. El sistema combina tracking basado en aristas, medidas del giroscopio, la gravedad y el campo mágnetico para proporcionar una localización precisa. Un año más tarde, Klein y Murray presentan un sistema capaz de realizar las tareas de tracking y mapping paralelamente, en dos hilos separados [23]. Es la primera aproximación a la técnica de SLAM, que describiremos posteriormente. A nales de la década, coincidiendo con el boom de los smartphones , comienzan a aparecer más entornos de desarrollo. En 2008, la compañía Metaio presenta una guía de museo con RA. Este mismo año nace Wikitude, que en sus inicios combina los datos del GPS y la brújula con entradas de Wikipedia para proporcionar información obtenida de 1 https://www.artoolkit.org/ Personalización de rutas en sistemas de turismo y ocio 11 CAPÍTULO 2. ESTADO DEL ARTE representa una ventaja sobre otras representaciones más convencionales como pueden ser listas de objetos o mapas. Pocas aplicaciones combinan la recomendación de rutas con la Realidad Aumentada. MoreTourism [33] utiliza etiquetas y pesos para recomendar puntos de interés. La recomendación se realiza comparando la nube de etiquetas del usuario con la nube de etiquetas de los puntos. Este trabajo también propone recomendaciones para grupos creando una nube de etiquetas de grupo usando las nubes de etiquetas de sus miembros. La información se presenta integrando la información, imágenes y videos mediante servicios de Realidad Aumentada. Otra aplicación que combina estas dos técnicas es RAMCAT [34], que presenta un sistema recomendador híbrido basado en contexto orientado a integrar Realidad Aumentada en dominios turísticos. La aplicación recomienda puntos de interés teniendo en cuenta preferencias personales y atributos contextuales. Existen varios módulos para estas recomendaciones: ltrado colaborativo, contextual, por contenido, etc. La información se puede presentar tanto aumentada como en un formato convencional de lista de puntos de interés. Además, el sistema se retroalimenta mediante las calicaciones de los turistas. En [35], los autores presentan una herramienta de aprendizaje para el ámbito académico que recomienda contenido en función de los intereses del usuario, presentándolo mediante una interfaz basada en Realidad Aumentada. Los intereses del usuario se extran del comportamiento del usuario al interactuar con el contenido presentado en la interfaz. Respecto a guiar a los usuarios hasta un punto, es interesante el enfoque de la aplicación Penguin NAVI 13 , que utiliza a un grupo de pingüinos como guías para llevar a los usuarios hasta el Sunshine Aquarium de Tokio. El éxito de esta aplicación supuso un aumento de la auencia del 150% con respecto al mes anterior. 2.3. Conclusiones En este capítulo hemos visto las principales nociones teóricas necesarias para la formalización del problema de la personalización de rutas. En primer lugar, se han introducido algunos conceptos sobre grafos que nos servirán para caracterizar el mapa del dominio, y sobre algoritmos de búsqueda para obtener caminos en el grafo. También hemos introducido los sistemas recomendadores y el razonamiento basado en casos. Por último, hemos estudiado las diferentes posibilidades que ofrecen las técnicas de Realidad Aumentada a a hora de mejorar la experiencia del usuario. Esto nos permitirá guiar al usuario por el recorrido recomendado o ampliar la información disponible. Las técnicas vistas servirán para implementar elementos de Realidad Aumentada en las recomendaciones. Si se trata de un dominio cuyas rutas son en interiores, deberemos utilizar técnicas basadas en marcadores, o utilizar un Sistema de Posicionamiento en Interiores para la localización. Por el contrario, en un entorno al aire libre podremos hacer uso del GPS para localizar nuestra posición y la de los puntos 13 http://penguinnavi.erba-hd.com/ 18 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 2. ESTADO DEL ARTE que deberemos visitar, aunque también tengamos la posibilidad de utilizar marcadores. Veremos las implementaciones de estas tecnologías en los casos de estudio del Museo García Santesmases (Sección 4.1) y del recomendador de turismo en Madrid (Sección 4.2). Personalización de rutas en sistemas de turismo y ocio 19 3 Marco teórico para la personalización de rutas En este capítulo se propondrá un marco teórico para la recomendación de rutas personalizadas. Este marco, que será adaptable a cualquier caso de estudio concreto, admitirá tanto recomendaciones individuales como grupales, y será aplicable a dominios con muchos puntos de interés seleccionables o con tan sólo unos pocos. Por otra parte, las rutas podrán ser en entornos interiores, como un museo o un centro comercial, o exteriores como en una ciudad. Etiquetaremos los puntos de interés según sus características e introduciremos las preferencias del usuario, creando itinerarios en los que, respetando un límite de tiempo, se visiten los puntos de interés cuyas etiquetas mejor se adecúen a estos gustos. 3.1. Formalización del problema a resolver El objetivo de nuestros algoritmos de planicación de rutas será encontrar una ruta para un individuo o un grupo de personas que recorra una secuencia de puntos de interés categorizados con diferentes etiquetas. La ruta debe maximizar la satisfacción de las preferencias del individuo o del grupo, descritas como un conjunto de pares de etiquetas y sus respectivos valores asociados. Además, la ruta ha de ajustarse al tiempo máximo proporcionado para la visita. Formalicemos ahora el problema a resolver. Sea V={v1, . . . , vp} un conjunto no vacío de puntos de interés, y sea K={k1, . . . , kn} un conjunto de etiquetas que describen tanto las características de los anteriores puntos de interés como las preferencias del grupo. Las etiquetas son dependientes del dominio. Cada punto de interés vi está caracterizado por Personalización de rutas en sistemas de turismo y ocio 21 CAPÍTULO 3. MARCO TEÓRICO PARA LA PERSONALIZACIÓN DE RUTAS un vector de preferencias vi.cov ={λk1, . . . , λkn} , con λkj∈[0,1] , que representan el grado en que vi cubre la etiqueta kj ; y un valor tvi que representa el tiempo recomendado para visitar el punto vi . Cada punto de interés tiene una localización. El mapa que representa las localizaciones de los puntos de interés está caracterizado como un grafo no dirigido G= (V, E) , donde E es un conjunto de aristas denidas como pares de puntos de interés < vi, vj> donde vi, vj∈V . Cada arista tiene asociado un valor t<vi,vj> que representa el tiempo empleado en desplazarse desde el punto vi al punto vj . Para la implementación de los algoritmos podremos asumir que G es un grafo dirigido, ya que el coste de recorrer una arista en sentido directo o inverso es el mismo. G es un grafo fuertemente conexo ya que para cualquier par de vértices vi y vj existe un camino de vi a vj de vj a vi . Un grupo de visitantes (la consulta en el algoritmo CBR) está caracterizado por una tupla (sizeq, ageq, prefq, tq) , donde size es el número de personas en el grupo, age es la edad media de sus miembros, prefk={λk1. . . λkq} con λki∈[0,1] es un conjunto de pesos que indican las preferencias del grupo para cada etiqueta y tq es la restricción temporal que indica la duración máxima de la visita. En el caso de que se trate de un único visitante, estará caracterizado por la tupla (prefq, tq, ageq) . La solución del problema será una ruta , una secuencia ordenada de puntos de interés R={v1, .., vm} con m paradas, donde vi∈V , y tR=Pm i=1 tvi+Pm−1 i=1 t<vi,vi+1> , con tR≤tq . Ahora ya sabemos cómo relacionar los gustos del usuario con los puntos a visitar, pero necesitaremos una función que indique qué puntos son mejores basándose en estos gustos. El problema de cómo medir el grado en el que una ruta cubre las preferencias del usuario (denidas como un conjunto de etiquetas asociadas a unos pesos) no es trivial. De acuerdo con [1], denimos el valor de cobertura como el grado en que las preferencias del usuario son cubiertas por la ruta escogida. Si tomamos K={k1, . . . , kn} como el conjunto de etiquetas anteriormente denido y λkq el valor asociado a la etiqueta kq , la función de cobertura de un camino R es: kc(R) = Xkq∈Kλkq·cov(kq, R) siendo cov(kq, R) el grado en el que la etiqueta kq está cubierta en el camino R , dado por: cov(kq, R)=1−Yvi∈R(1 −vi.cov(kq)) Esta función de cobertura cumple que es submodular , es decir, que kc(R1∪vi)−kc(R1)≥kc(R2∪vi)−kc(R2) con R1⊆R2 y vi6∈ R1 . Esta propiedad se utilizará para la demostración de la admisibilidad de h . El valor kc(R) usado es adecuado para rutas con un número reducido de puntos de 22 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 3. MARCO TEÓRICO PARA LA PERSONALIZACIÓN DE RUTAS interés. No obstante, para grafos grandes la diferencia entre los valores de cobertura de las rutas correspondientes a visitar todos los objetos del museo frente a las rutas que visitan tan solo la mitad es muy pequeña. Por esta razón denimos una nueva función de cobertura: kc _ sum(R) = Xvi∈Rvi.cov(K) (3.1) donde vi.cov(K) : vi.cov(K) = Xkj∈Kλj·vi.cov(kj) Esta función no tiene en cuenta la diversidad de las categorías visitadas en la ruta, pero como asumimos que visitamos una gran cantidad de puntos de interés, esta pérdida no supone un gran problema. Además, nos permitirá añadir puntos a la ruta con más facilidad, pues la cobertura de cada punto ya no depende del resto de la ruta. Nótese que kc_sum también es una función submodular, ya que: kc _ sum(R1∪vi)−kc _ sum(R1) = vi.cov(K) 3.2. Desarrollo del problema Con las deniciones que hemos proporcionado, estamos en disposición de formular un algoritmo para planicación de rutas personalizadas en un grafo. Este algoritmo tendrá en cuenta el contenido de cada nodo, personalizando el camino elegido en función de las preferencias del usuario. Por tanto, además del grafo, formado por el conjunto de vértices V y el conjunto de aristas E , el algoritmo necesitará estas preferencias ( prefq ). 3.2.1. Algoritmo A ? modicado El primer algoritmo que utilizaremos para encontrar la ruta óptima dentro del grafo es una modicación del Algoritmo A ? , puesto que así obtendremos la solución óptima para la heurística que hayamos elegido, siempre y cuando esta sea admisible. Para ello, seguimos el algoritmo ORS-KC presentado en [1]. Para implementar el algoritmo A ? necesitaremos denir la función de evaluación f , que será: fn(Rs→t) = gn(Rs→n) + hn(Rn→t|Rs→n), donde g calcula el valor exacto de cobertura de la ruta Rs→n , mientras que h estima el valor de cobertura del resto de la ruta condicionado a la parte ya recorrida. Pasemos ahora a denir la función heurística h y demostrar su admisibilidad. Personalización de rutas en sistemas de turismo y ocio 23 CAPÍTULO 3. MARCO TEÓRICO PARA LA PERSONALIZACIÓN DE RUTAS Admisibilidad de la función heurística Como la función kc es submodular, h es la cobertura del resto de la ruta Rs→n , en lugar de la cobertura de la ruta Rn→t . Así, en lugar de estimar kc(Rs→n) , calcularemos kc(Rs→n)−kc(Rs→n) . Tal y como se demuestra en [1], kc(Rs→n)−kc(Rs→n)≤(m´ax kq∈KY vi∈Rs→n [1 −covkq(vi)]) ·kc(Rn→t), donde denimos hn(Rn→t|Rs→n) = (m´axkq∈KQvi∈Rs→n[1 −covkq(vi)]) ·kc(Rn→t) . Para asegurarnos de la admisibilidad de h , calcularemos una cota superior de kc(Rn→t) utilizando el algoritmo voraz, cuya implementación concreta veremos más adelante en el Algoritmo 3. Este algoritmo alcanza un factor de aproximación de 1−1 √e , es decir, kc(Lop)≤kc(Lv) 1−1 √e , donde Lop es el conjunto óptimo de nodos mientras que Lv es el conjunto de nodos calculados por el algoritmo voraz. Se puede encontrar en [1] la prueba de que kc(Rn→t)≤kc(Lv) 1−1 √e , con lo que la denición de h queda hn(Rn→t|Rs→n) = (m´ax kq∈KY vi∈Rs→n [1 −vi.cov(K)]) ·kc(Lv) 1−1 √e ), que cumple la admisibilidad requerida por A ? , pues hemos visto que no estima por encima del coste real. Por tanto, nalmente f se calcula como fn(Rs→t) = kc(Rs→n)·(m´ax kq∈KY vi∈Rs→n [1 −vi.cov(K)]) ·kc(Lv) 1−1 √e Descripción del algoritmo Una vez denida la función heurística h y demostrada su admisibilidad, podemos explicar el funcionamiento del Algoritmo 2. El algoritmo comienza creando una ruta vacía con valor de cobertura −∞ , donde almacenaremos la mejor ruta que vayamos calculando. También crearemos una cola de prioridad de rutas ordenada por valor decreciente de la función f . Mientras esta cola no esté vacía, tomaremos el primer elemento y comprobaremos que la estimación de su valor heurístico es mayor que el valor de cobertura de la mejor ruta hallada hasta el momento. Si no lo fuera, la ruta guardada sería la óptima, ya que al tratarse de una cola de prioridad, todas las rutas almacenadas en ella tendrán un valor heurístico igual o peor que la que hemos tomado. 24 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 3. MARCO TEÓRICO PARA LA PERSONALIZACIÓN DE RUTAS Si el valor heurístico de Rk i es mayor que la mejor cobertura encontrada hasta el momento( kcmax ), añadiremos un nuevo nodo a esa ruta, asegurándonos de no sobrepasar el tiempo máximo tq del que disponemos para recorrer la ruta. Si el nodo que hemos añadido es el último vértice del grafo, comprobaremos si el valor heurístico de la ruta obtenida es mayor que el de la ruta que teníamos guardada como mejor, y en caso armativo la sustituiremos por la actual. Si la función heurística de la ruta actual proporciona un valor mayor que el de la ruta almacenada, la guardaremos como la mejor y si no hemos llegado al último nodo la almacenaremos en la cola de prioridad. Cuando no queden más nodos en la cola de prioridad Q habremos acabado, y devolveremos la ruta R almacenada. Algoritmo 2: ORS-KC [1] MaxPriorityQueue Q=∅ ; Route R=∅ ; double kcmax =−∞ ; Route Rs 0= (vs) ; Q. push(Rs 0) ; while Q is not empty do Rk i=Q.get() ; if f(Rk i)≤kcmax then break; end for cada arista ( vi, vj ) do Rl j=Rk i.add(vj) ; if bs(Rl j> tq) then continue; end if ( vs=vt ) then if (kc(Rl j)> kcmax) then R=Rl j ; kcmax =kc(Rjl) ; end else if f(Rl j> kcmax) then Q.push(Rl j); end end end end if ( kcmax == −∞ ) then return No hay ruta posible; else return R; end Personalización de rutas en sistemas de turismo y ocio 25 CAPÍTULO 3. MARCO TEÓRICO PARA LA PERSONALIZACIÓN DE RUTAS Veamos un ejemplo que nos ayude a entender las deniciones y el algoritmo. Consideremos el grafo de la Figura 3.1, y supongamos las siguientes preferencias del usuario: Historia : 0,6; entretenimiento : 0,4; museo : 0,2; monumento : 0,1. 1 monumento 0.8 Historia 0.2 1 2 entretenimiento 0.8 museo 0.3 1 3 1 Historia 0.8 museo 0.1 4 Historia 0.6 museo 0.4 1 5 1 Historia 0.7 6 Historia 0.5 1 1 2 5 4 5 6 7 Figura 3.1: Grafo de ejemplo Analicemos los caminos superior (vértices 1, 2, 4 y 6) e inferior (1, 3, 5 y 6). El camino inferior a priori nos proporcionaría mayor satisfacción, pues la etiqueta historia es la que mayor ponderación tiene entre los gustos del usuario. No obstante, como hemos comentado, el algoritmo A ? tiene en cuenta la diversidad de las etiquetas de la ruta, por lo que escogerá el camino superior. Al tratarse de una variante del algoritmo A ? , que es completo, es comprensible que el tiempo de cálculo para obtener la solución sea grande en dominios con muchos puntos de interés. La ejecución del algoritmo A ? tarda más de 104 segundos en un grafo de 22 vértices [36]. Esto puede ocasionar problemas en las aplicaciones prácticas del recomendador, como puede ser el uso en una aplicación móvil. Para ello, se han propuesto diferentes algoritmos que, sin ser tan exhaustivos como A ? , siguen proporcionando buenas soluciones. 3.2.2. Algoritmo voraz Recordemos que en el algoritmo A ? necesitamos hacer una estimación del camino restante hasta alcanzar el último nodo. Para ello, en nuestra implementación hemos utilizado el algoritmo voraz presentado en [37]. Sin embargo, en el caso de un grafo fuertemente conexo, donde cada nodo está conectado a todos los demás, el algoritmo A ? está considerando demasiadas restricciones que no son necesarias. Presentemos teóricamente el algoritmo voraz. Cuando introducimos el algoritmo A ? , vimos que constaba de 2 funciones, g y h que representaban el coste exacto del camino 26 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 3. MARCO TEÓRICO PARA LA PERSONALIZACIÓN DE RUTAS recorrido y la estimación heurística del camino por recorrer. El algoritmo voraz sólo tiene en cuenta la función h , es decir, el coste estimado del camino más corto desde el nodo en el que nos encontramos hasta el nodo nal [3]. La idea al utilizar este algoritmo es obtener una lista ordenada de los vértices que mayor relación guardan con los gustos del usuario. Después, basta con ordenar estos nodos para obtener un camino. Como el algoritmo A ? proporcionaba caminos que partían del vértice inicial del grafo, debemos forzar que este vértice aparezca en la solución voraz, con lo que lo quitaremos de la entrada del algoritmo, añadiéndolo al ordenar la salida obtenida. El coste del algoritmo voraz es lineal respecto al tamaño de la entrada n, lo que lo hace mucho más rápido que el A ? . Para nuestra implementación deberemos denir cuándo es factible la solución, y cuál es el criterio del algoritmo voraz. La solución (es decir, el conjunto de nodos) será factible siempre y cuando la suma de sus tiempos no supere el límite tq establecido en la formalización del problema. Para calcular los tiempos entre aristas, dado que se trata de un conjunto de nodos y no un camino, deberemos denir una función: vi.cost() = m´ın vj∈G{t<vj,vi>} donde el vértice inicial cumple vs.cost() = 0 . Por otra parte, el criterio según el cual seleccionará el algoritmo voraz deberá tener en cuenta las características de los nodos, los gustos del usuario y el tiempo empleado en visitar el nodo. Por tanto, se ha optado por el cociente vi.cov(K) vi.cost()+tvi . La implementación nal del algoritmo voraz se puede ver en el Algoritmo 3. Algoritmo 3: Algoritmo Voraz Function ItemList CBRRouteFinding(Graph G=(V,E), double tq ) ItemList U = V; Route R = {}; double max = 0; int maxindex = -1; while (|U|>0) do max =∞ ; for (vi∈U) do if (vi.cov(K) vi.cost()+tvi> max) then maxindex = i; max = vi.cov(K) vi.cost()+tvi ; end end if (tR+vmax.cost() + tvmax )< tq) then R=R∪vmax ; end U=U\vmax ; end Personalización de rutas en sistemas de turismo y ocio 27 CAPÍTULO 4. CASOS DE ESTUDIO actualidad. Estas piezas, aunque tienen en común su relación con el mundo de la informática, varían desde los primeros ordenadores digitales hasta los últimos modelos de servidores, pasando por procesadores, videoconsolas y diversos periféricos. El objetivo es personalizar las rutas que recorran los visitantes según las distintas inquietudes que tengan y el tiempo del que dispongan para la visita. Durante el proceso de adquisición de conocimiento del dominio hemos observado que se pueden realizar rutas temáticas para diversos grupos, como pueden ser estudiantes de informática, interesados por categorías como hardware , servidores o redes , personas mayores, que preeren contenidos relacionados con historia , España o curiosidad , cinélos, interesados por cine y curiosidad , niños que muestran preferencia por videojuegos , etc. Además, queremos mejorar la experiencia de los visitantes utilizando Realidad Aumentada, de manera que se les presente la información de una forma novedosa que les haga interesarse por los contenidos del museo. Dado que el museo se encuentra en un edicio, deberemos utilizar tecnologías de Realidad Aumentada en interiores, como pueden ser Sistemas de Posicionamiento en Interiores o marcadores. 4.1.1. Resolución del problema Para poder aplicar las técnicas vistas en el Capítulo 2.1.1 debemos formalizar el problema según se explicó en la Sección 3.1. En primer lugar denamos el grafo que recorreremos. Los nodos que lo forman son las distintas vitrinas del museo, que están compuestas por una o más piezas. La lista detallada de las vitrinas se puede encontrar en el Apéndice A. Dado que el museo consta de dos plantas, uniremos los subgrafos que formarían cada una de ellas en un sólo grafo, cuyos vértices se muestran en la Figura 4.1. Además, cada nodo tendrá los siguientes atributos. Identicador: un número del 1 al 52 que indica de qué vitrina se trata. Descripción: breve descripción de la(s) pieza(s) que componen la vitrina. Tiempo: minutos que se recomienda tardar en examinar la vitrina. Etiquetas: conjunto de pares <Etiqueta, Valor> que categorizan la vitrina, asignando un valor entre 0 y 1 a las distintas etiquetas. En caso de que la vitrina cuente con más de una pieza, se ponderarán los valores de las etiquetas de las piezas que la compongan. Las etiquetas del museo se han identicado en un proceso de ingeniería del conocimiento, y son: almacenamiento , arte , ciencias , cine , curiosidad , docencia , España , Facultad de Informática , hardware , Historia , PCs , periféricos , redes , servidores y videojuegos . 34 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 4. CASOS DE ESTUDIO Figura 4.1: Nodos del Museo García Santesmases Al ser un museo, donde nos podemos desplazar libremente, todos los nodos están conectados entre sí. Las aristas del grafo serán las distancias en tiempo entre los puntos, que en este caso concreto son casi nulas debido a la proximidad entre las distintas vitrinas. Aún así deberemos tenerlas en cuenta para el correcto funcionamiento del algoritmo. Para automatizar la generación de estas aristas, calculado la distancia entre dos nodos en función de la distancia geográca en el grafo anterior, con alguna peculiaridad, que a continuación se explica. El museo está dividido en 4 zonas: cada ala de cada planta es una zona diferente. Para calcular la distancia entre dos puntos, comprobaremos a qué zona pertenecen. Si ambos están en la misma zona, la distancia entre ellos será la distancia geográca en el grafo multiplicada por una constante empírica que representa la velocidad, de tal forma que resulte la distancia en tiempo entre los dos puntos. Si los dos puntos pertenecen a distintas zonas, calcularemos la distancia desde el primer punto al punto de cambio de zona (si las dos zonas están en la misma planta será el lateral de la planta, en caso contrario las escaleras) y desde ahí al segundo punto. Ahora que ya disponemos de los nodos del grafo y de las aristas que los unen, podemos Personalización de rutas en sistemas de turismo y ocio 35 CAPÍTULO 4. CASOS DE ESTUDIO ejecutar los algoritmos. Para ello necesitaremos describir la visita. No podremos utilizar el algoritmo A ? , pues el grafo consta de 52 nodos y no podría calcular la ruta personalizada en un tiempo razonable. El algoritmo voraz calcula una ruta que se adecúa a las preferencias introducidas por el usuario o el grupo, así como al tiempo del que dispone para la visita al museo. El algoritmo CBR además de las preferencias y el tiempo, recibirá como entrada la edad del usuario, o el tamaño del grupo y su edad media, en el caso de grupos. Una vez tenga todos los datos, el algoritmo devolverá la lista ordenada de nodos que deberá visitar, así como el tiempo que deberá gastar en cada uno de ellos. Los casos del algoritmo CBR han sido adquiridos durante un proceso de observación de visitas reales al MIGS durante un mes, a los que se han sumado otros proporcionados por el experto del dominio (José Luis Vázquez-Poletti). El conjunto de casos consta de 28 casos prototípicos que cubren diferentes situaciones de visitas grupales, como grupos de varios tamaños de distintos alumnos de grados universitarios, másters o doctorados; visitas rápidas para diferentes grupos de las vitrinas más importantes del museo, visitas para niños, adultos y personas mayores, visitas temáticas con diferentes intereses (general, cine, videojuegos, historia). La Figura 4.2 visualiza el caso base como un grafo. Los nodos representan los casos y las aristas la similitud entre casos. El grosor de las aristas se ha calculado con la función de similitud . Figura 4.2: Base de casos representada como un grafo Los valores correspondientes a la función de distancia denida en la Sección 3.2.3 son constTime = 0.4, constSize = 0.2, constAge = 0.1 y constLabel =0.5. Los pesos reejan la importancia de las diferentes variables. La relevancia de la edad es menor puesto que se ha observado una dependencia entre edad y preferencias, es decir, algunas de las preferencias grupales pueden depender de la edad y son cubiertas por las distintas etiquetas en la consulta. 36 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 4. CASOS DE ESTUDIO 4.1.2. Recorridos de prueba Para comparar los algoritmos voraz y CBR, estudiaremos una serie de recorridos personalizados para varios grupos de usuarios con gustos diferentes, correspondientes a visitas indicadas por el experto en el dominio. Los grupos seleccionados serán alumnos de informática, interesados en categorías como FDI , redes o hardware , alumnos de ciencias, con preferencia por vitrinas relacionadas con ciencias o curiosidad y pesonas mayores, que desean visitar objetos relacionados con las etiquetas historia , España , curiosidad . Alumnos de Informática Contemplemos primero la recomendación para un grupo de alumnos de la Facultad de Informática que disponen de una hora para visitar el museo. La tupla (sizeq, ageq, prefq, tq) que caracteriza las visitas en el algoritmo CBR será (20,20, prefq,60) , donde prefq se corresponde con las preferencias que se exponen a continuación. Almacenamiento: 0,65 Arte: 0,4 Ciencias: 0,6 Cine: 0,5 Curiosidad: 0,7 Docencia: 0,4 España: 0,6 FDI: 0,9 Hardware: 0,65 Historia: 0,6 PCs: 0,9 Periféricos: 0,6 Redes: 0,6 Servidores: 0,6 Videojuegos: 0,9 Las rutas recomendadas para ellos pueden verse en la Figura 4.3. En ella aparecen en color verde los puntos de interés seleccionados por el algoritmo voraz, en azul los escogidos por el CBR, y en rojo los que han sido recomendados por ambos algoritmos. Vemos que tanto la ruta recomendada por el algoritmo voraz como la elegida por el CBR constan de 36 nodos, de los cuales 29 son comunes. Entre ellos se encuentran los elementos más representativos del museo, como el Supercomputador Cerebro, el primer minicomputador de España, el Friden EC-132 con el tubo de rayos catódicos, el simulador de centrales térmicas, los ordenadores Amstrad o las obleas de silicio. Las vitrinas elegidas en cada ruta son: Voraz: 1, 2, 3, 4, 8, 10, 11, 13, 14, 15, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 40, 43, 45, 46, 47, 48, 49, 51, 52. CBR: 1, 2, 3, 4, 6, 8, 10, 11, 13, 14, 15, 20, 23, 24, 26, 29, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 48, 49, 50, 51, 52. Personalización de rutas en sistemas de turismo y ocio 37 CAPÍTULO 4. CASOS DE ESTUDIO Comunes: 1, 2, 3, 4, 8, 10, 11, 13, 14, 15, 20, 23, 24, 26, 29, 31, 33, 35, 36, 37, 38, 39, 40, 43, 45, 48, 49, 51, 52. Sólo voraz: 19, 22, 28, 30, 39, 46, 47. Sólo CBR: 6, 34, 39, 41, 42, 44, 50. Con respecto a las pequeñas diferencias entre ambas rutas, el algoritmo voraz escoge los nodos 28 y 30, correspondientes a los ordenadores Amstrad y con una alta valoración en la etiqueta videojuegos . Por contra, el algoritmo CBR rescata la visita de alumnos de informática en clase, que cuenta con unas preferencias muy similares a nuestra visita, pero con menor valor en el campo de videojuegos. Por tanto, en lugar de elegir esos dos nodos, se preere profundizar en las vitrinas que abarcan desde el punto 38 al 43. En este caso, además de tratar contenidos más relacionados con el temario de las asignaturas de la carrera, se puede desarrollar una explicación conjunta de todas las vitrinas, conectando unas con otras. Figura 4.3: Ruta recomendada para alumnos de Informática 38 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 4. CASOS DE ESTUDIO Alumnos de carreras de ciencias Continuemos ahora con el caso de un grupo de alumnos de un máster en ciencias que dispongan de una hora para realizar una visita al museo. En este caso, la tupla que caracterizará las visita en el algoritmo CBR será (30,25, prefq,60) , donde las preferencias prefq corresponden los gustos que se presentan a continuación. Almacenamiento: 0,3 Arte: 0,5 Ciencias: 0,9 Cine: 0,4 Curiosidad: 0,9 Docencia: 0,5 España: 0,7 FDI: 0,4 Hardware: 0,2 Historia: 0,7 PCs: 0,5 Periféricos: 0,2 Redes: 0,3 Servidores: 0,2 Videojuegos: 0,6 Las rutas recomendadas para ellos pueden verse en la Figura 4.4. Las vitrinas elegidas en cada ruta son: Voraz: 1, 2, 3, 4, 7, 8, 10, 11, 12, 14, 15, 16, 17, 19, 20, 22, 23, 24, 26, 28, 29, 30, 31, 33, 34, 35, 36, 37, 38, 45, 47, 48, 49, 51. CBR: 1, 2, 3, 4, 6, 9, 11, 12, 14, 15, 18, 19, 23, 28, 29, 30, 31, 34, 35, 36, 38, 40, 43, 45, 46, 48, 50, 51, 52. Comunes: 1, 2, 3, 4, 11, 12, 14, 15, 19, 23, 28, 29, 30, 31, 34, 35, 36, 38, 45, 48, 51. Sólo voraz: 7, 8, 10, 16, 17, 20, 22, 24, 26, 33, 37, 47, 49. Sólo CBR: 6, 9, 18, 40, 43, 46, 50, 52. De nuevo vemos en color verde los puntos de interés elegidos por el algoritmo voraz, en azul los que ha recomendado el algoritmo CBR y en rojo los comunes a ambos algoritmos. Al igual que en la visita anterior, elementos representativos del museo como el primer minicomputador de España, los ordenadores Amstrad o las obleas de silicio han sido escogidos por ambos algoritmos. En este caso la visita recuperada era de alumnos del máster en Bioinformática, que aunque comparten unas preferencias similares con los alumnos de ciencias muestran más interés por la informática, por lo que la visita se centra más en la parte de PCs y servidores (por ejemplo visitando los discos duros y el CRAY Y-MP EL). Por su parte, el algoritmo voraz se centra más en los objetos de la primera parte del museo, de carácter más general, como pueden ser los teléfonos móviles o el perro robótico Sony AIBO ERS-7. Personalización de rutas en sistemas de turismo y ocio 39 CAPÍTULO 4. CASOS DE ESTUDIO Figura 4.4: Ruta recomendada para alumnos de ciencias Personas mayores Por último, consideremos un grupo de personas mayores que se disponen a realizar una visita al museo, para la que disponen de 40 minutos. La tupla correspondiente a esta visita será (30,65, prefq,60) , donde las preferencias prefq han sido modelizadas como se expone a continuación. Almacenamiento: 0,2 Arte: 0,6 Ciencias: 0,5 Cine: 0,6 Curiosidad: 0,9 Docencia: 0,6 España: 0,8 FDI: 0,3 Hardware: 0,3 Historia: 0,9 PCs: 0,4 Periféricos: 0,3 Redes: 0,2 Servidores: 0,2 40 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 4. CASOS DE ESTUDIO Videojuegos: 0,1 La ruta recomendada para ellos puede verse en la Figura 4.5. Las vitrinas elegidas en cada ruta son: Voraz: 1, 2, 3, 4, 7, 8, 10, 11, 14, 15, 19, 20, 22, 23, 28, 30, 31, 36, 38, 40, 48. CBR: 1, 2, 4, 6, 8, 10, 14, 15, 20, 22, 28, 29, 30, 31, 34, 36, 37, 45, 46, 48, 51. Comunes: 1, 2, 4, 8, 10, 14, 15, 20, 22, 28, 30, 31, 36, 48. Sólo voraz: 3, 7, 11, 19, 23, 38, 40. Sólo CBR: 6, 29, 34, 37, 45, 46, 51. En primer lugar observamos que tanto el agoritmo voraz (verde) como el CBR (azul) recomiendan una ruta de 21 nodos, de los cuales 14 son comunes a ambos algoritmos (un 66% del total). Entre los nodos que no lo son, se puede ver cómo el algoritmo voraz recomienda ítems de categorías variadas, pero que interesan al grupo, mientras que el CBR realiza alguna recomendación que no se ajusta a los gustos de los usuarios (por ejemplo tanto el IBM 7090 como las consolas Atari y Nintendo están etiquetados con la categoría videojuegos , que no interesa a los visitantes. Esto se debe a que el caso que ha recuperado el algoritmo (una visita de padres de alumnos de la facultad) presenta ligeras diferencias en los valores de las preferencias de los usuarios. Conclusiones Con los tres casos tratados anteriormente podemos concluir que ambos algoritmos proporcionan recomendaciones acertadas de rutas en el museo. La diferencia entre las rutas propuestas entre ambos es baja siempre que se cuente con recomendaciones para grupos similares en la base de casos. A continuación presentaremos una comparativa entre ambos algoritmos donde se han realizado una gran cantidad de consultas a ambos recomendadores aleatorizando las variables que conforman dichas consultas. 4.1.3. Comparación del algoritmo voraz con el algoritmo CBR El propósito de la evaluación es comparar los valores de la función de cobertura kc _ sum(R) descrita anteriormente, de acuerdo a los atributos de tamaño, tiempo disponible para la visita, edad media y preferencias del grupo. El experimento consistirá en una serie de tests que evalúen el impacto de cada atributo en la consulta de forma independiente, y las diferencias entre los resultados obtenidos por los algoritmos voraz y CBR. Para ello, cada atributo evaluado es jado a diferentes valores, y los demás atributos se generan de manera aleatoria. El atributo correspondiente a las Personalización de rutas en sistemas de turismo y ocio 41 CAPÍTULO 4. CASOS DE ESTUDIO Figura 4.5: Ruta recomendada para mayores preferencias del grupo se ha jado a tres conjuntos que representan tres visitas prototípicas (intereses neutros, estudiantes de Ingeniería Informática y personas mayores). En cada test se han generado 400 consultas para cada valor jado. Para cada experimento hemos medido el valor de la función de cobertura kc _ sum (R) y hemos normalizado el resultado obtenido con respecto a una consulta equivalente que representa una visita que recorre todos los puntos de interés. Finalmente hemos calculado el valor medio para las 400 consultas, deniendo un porcentaje medio de cobertura. Resultados Experimentales Como es esperable, el algoritmo voraz ofrece mejores resultados en términos de cobertura, aunque vemos que el Algoritmo CBR también muestra buenos resultados con un tiempo de respuesta muy eciente. La Figura 4.6 muestra algunos de los resultados experimentales obtenidos al jar la longitud de la visita ( tq ) en la consulta. Los resultados muestran, como era de esperar, 42 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 4. CASOS DE ESTUDIO que la cobertura de la ruta aumenta al aumentar el tiempo disponible para la visita. 90 minutos dan suciente tiempo a los visitantes como para visitar todos los puntos de interés del museo, por lo que las preferencias del grupo no afectan a la ruta. No obstante, podemos observar que la cobertura obtenida por el algoritmo CBR es menor en los grupos grandes incluso en una visita de 90 minutos donde todos los nodos son elegidos en la solución obtenida por el algoritmo voraz. Esto se debe a las restricciones de espacio que han sido capturadas como conocimiento en los casos. Los casos nos permiten observar que los grupos grandes nunca se paran en las vitrinas pequeñas. Eso también explica por qué la cobertura es menor en el caso del CBR aun cuando hay suciente tiempo como para visitar todos los nodos. El algoritmo voraz no tiene en cuenta el conocimiento experto y por tanto genera rutas que no son adecuadas para grupos grandes. Figura 4.6: Comparación para diferentes valores de tiempo disponible En la Figura 4.7 observamos los valores de la cobertura para grupos de diferente tamaño ( sizeq ). Vemos cómo la cobertura apenas varía con los distintos tamaños de grupo analizados. Como hemos mencionado anteriormente, la cobertura es menor en grupos grandes debido a las restricciones de espacio en el museo, ya que el algoritmo voraz proporciona visitas que nunca se podrían llevar a cabo con grupos grandes. Figura 4.7: Comparación para diferentes valores de tamaño de grupo Personalización de rutas en sistemas de turismo y ocio 43 CAPÍTULO 4. CASOS DE ESTUDIO Turismo En este recorrido, el grupo de visitantes serán turistas, cuyas preferencias son principalmente entretenimiento , gastronomía y monumento , mostrando un interés nulo por la categoría infantil . Veamos las rutas recomendadas por el algoritmo A ? (verde) y voraz (azul) en la Figura 4.15. Figura 4.15: Recomendación para turistas Hay cinco nodos elegidos por los dos algoritmos: la Puerta del Sol, la Plaza Mayor, el Mercado de San Miguel, el Palacio Real y la Catedral de la Almudena. El alto valor de la etiqueta gastronomía lleva a los algoritmos a escoger el Mercado de San Miguel, mientras que las elecciones del Palacio Real y la Catedral de la Almudena se sustentan en que cubren tres etiquetas distintas cada uno. En este caso, el algoritmo voraz opta por visitar el barrio de La Latina, con buenos valores en gastronomía y entretenimiento , y la Puerta de Alcalá ( monumento ), mientras que el A ? elige el Parque de El Retiro, con un valor muy alto en entretenimiento , categoría que apenas ha sido cubierta en el recorrido. Mayores Por último, nuestro grupo de visitantes serán personas mayores, con alto interés por las categorías de iglesia , monumento e historia , mostrando también un interés nulo por la categoría infantil , y valores bajos en gastronomía y entretenimiento . Veamos las rutas recomendadas por el algoritmo A ? (verde) y voraz (azul) en la Figura 4.15. De nuevo, tanto el algoritmo voraz como el A ? eligen 5 nodos en común: la Puerta del Sol, la Plaza Mayor, el Teatro Real, la Catedral de la Almudena y la Puerta de Alcalá. El alto interés por las categorías de historia , iglesia y monumento lleva a la elección del 50 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 4. CASOS DE ESTUDIO Figura 4.16: Recomendación para personas mayores Teatro Real, la Catedral de la Almudena y la Puerta de Alcalá, respectivamente. Para este grupo, el algoritmo voraz opta por visitar el Monasterio de las Descalzas Reales y el Palacio Real, apoyándose en los altos valores de las etiquetas iglesia e historia respectivamente. Por su parte, el algoritmo A ? elige el Museo del Prado, que cubre la etiqueta de arte , no considerada en el resto del recorrido. Conclusión de las visitas En las tres visitas hemos visto cómo los algoritmos A ? y voraz proporcionaban buenas recomendaciones en función de las preferencias de los grupos de usuarios a considerar. Ambos algoritmos coincidían en gran parte de la recomendación, variando ligeramente debido a las diferentes características de sus heurísticas. Como la heurística utilizada por el algoritmo A ? se preocupa más por la variedad de las etiquetas, las elecciones que diferían del algoritmo voraz se debían precisamente a incluir categorías no consideradas en el resto del recorrido. Por su parte, la heurística del algoritmo voraz se preocupa de obtener la máxima cobertura en cada punto de interés sin tener en cuenta los demás, tratando de maximizar la satisfacción del usuario, en ocasiones a costa de recomendar rutas ligeramente monotemáticas. 4.2.3. Prototipo de aplicación con Realidad Aumentada Con el objetivo de enriquecer la experiencia del usuario utilizando realidad aumentada, utilizaremos la señal GPS de nuestro teléfono para ubicar los diferentes puntos de interés. Facilitaremos el manejo alojando estos puntos en un servidor, al que nos conectaremos desde la aplicación. Personalización de rutas en sistemas de turismo y ocio 51 CAPÍTULO 4. CASOS DE ESTUDIO Así, una vez hayamos obtenido las coordenadas de los diferentes puntos, mostraremos unas tarjetas en cada uno de estos puntos donde aparezca el nombre del punto, la distancia hasta él, y una descripción del lugar. También mostraremos un radar donde aparezcan los puntos, permitiendo ajustar la distancia máxima hasta la que se mostrarán los ítems. En la Figura 4.17 podemos ver una captura de la aplicación donde se muestran varios tarjetas asociadas a puntos de interés recomendados (Círculo de Bellas Artes, Monasterio de las Descalzas Reales, Palacio Real). En la imagen de la derecha vemos la información correspondiente al Monasterio de las Descalzas Reales, así como la distancia a la que nos encontramos de él. Figura 4.17: Realidad Aumentada en el recomendador en Madrid 4.2.4. Conclusiones En este capítulo hemos podido explicado la implementación sobre dos casos de estudio muy diferentes entre sí del marco teórico denido en el Capítulo 3. En el Museo García Santesmases nos encontramos en un edicio de dos plantas, donde los puntos de interés apenas están separados unos pocos metros entre sí. En este caso optamos por generar las aristas automáticamente según la posición de los puntos en el mapa dado el poco impacto de las distancias en la elección de los puntos de la ruta. Dado que se detectaron 52 puntos de interés, la aplicación del algoritmo A ? resultaba inviable, por lo que se optó tanto por el algoritmo voraz como por el basado en casos. La comparación experimental entre ambos algoritmos concluyó que las recomendaciones proporcionadas por el algoritmo voraz son ligeramente mejores, aunque el algoritmo CBR permite incluir conocimiento de situaciones reales y especícas del dominio. Por otra parte, para mejorar la experiencia del usuario, y dado que la precisión de la 52 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 4. CASOS DE ESTUDIO localización en interiores imposibilitaba guiar al usuario mediante Realidad Aumentada, se colocaron marcadores en las vitrinas del museo que permitían al usuario obtener información adicional de forma interactiva. En cuanto al recomendador de turismo en Madrid, su reducido tamaño sí permitía la aplicación del algoritmo A ? , junto al que se usó el algoritmo voraz. En esta ocasión, puesto que las distancias entre puntos podían alcanzar los 30 minutos, se decidió obtener esas distancias de forma precisa, utilizando Google Maps para calcular el tiempo requerido, ya fuese andando o en transporte público. Dada su localización en exteriores, es posible el uso de la señal GPS del smartphone para localizar los distintos puntos de interés y guiar al usuario hacia ellos. Por tanto, aunque las diferencias entre los dos casos de estudio fuesen sustanciales, la amplitud del marco nos ha posibilitado encontrar aproximaciones para proporcionar rutas satisfactoriamente en ambos casos, aplicando los pasos enumerados en la Sección 3.3. Personalización de rutas en sistemas de turismo y ocio 53 5 Conclusiones y trabajo futuro 5.1. Conclusiones En este trabajo hemos planteado una solución genérica al problema de planicación de rutas personalizadas para individuos y grupos. Tras estudiar las técnicas de personalización de rutas, hemos propuesto tres algoritmos diferentes (A ? , voraz y basado en casos) que nos han permitido resolver el problema. Posteriormente, hemos aplicado el modelo teórico a dos casos concretos: el Museo García Santesmases y la personalización de rutas de turismo en Madrid. La aplicación de los algoritmos propuestos sobre estos casos ha permitido realizar una comparativa experimental entre ellos. Además, se han realizado prototipos de aplicaciones móviles que pretenden guiar al usuario durante el recorrido de las rutas en ambos dominios. A continuación expondremos algunos resultados especícos obtenidos en el trabajo. Respecto a los algoritmos propuestos, A ? proporciona una solución óptima, aunque no es ecaz para grafos con más de 15 nodos, pues sus tiempos de cálculo son muy grandes. El algoritmo voraz sí que se puede escalar a casos como el expuesto en la Sección 4.1, que contaba con 52 nodos. Por último, el algoritmo CBR permite incluir la información experta del dominio en la recomendación, realizando buenas recomendaciones con una base de casos relativamente pequeña. En los experimentos en el Museo García Santesmases se ha comparado la aproximación CBR a la búsqueda heurística utilizando la cobertura para medir cómo se ajusta la ruta recomendada a las preferencias de los usuarios. Los resultados permiten sintetizar las ventajas de utilizar el enfoque CBR para resolver este problema. Puesto que el algoritmo voraz realiza una búsqueda exhaustiva, sus resultados en cobertura mejoran Personalización de rutas en sistemas de turismo y ocio 55 CAPÍTULO 5. CONCLUSIONES Y TRABAJO FUTURO los del enfoque CBR. No obstante, los casos han resultado una forma excelente de obtener conocimiento experto proviniente de situaciones reales, como el hecho de que en grandes grupos hay limitaciones de espacio en las vitrinas. Otra ventaja del algoritmo CBR es que funciona incluso con un conjunto vacío de preferencias, por lo que es aplicable con menos conocimiento en la consulta. Sobre el caso de uso del recomendador de turismo en Madrid visto en la Sección 4.2, es interesante ver cómo el algoritmo A ? y el voraz coinciden en la mitad de los puntos recomendados. Las diferencias entre ambos están fundamentadas en la preferencia del algoritmo A ? por las rutas más variadas, mientras que el voraz se centra en recomendar al usuario las categorías que este preere, aunque resulte en rutas monotemáticas. Así, podrían ofrecerse ambas opciones al usuario para que este elija la que preera. Por último, la aplicación de técnicas de Realidad Aumentada sobre las rutas personalizadas ha resultado una forma sencilla e intuitiva para que el usuario pueda seguir el camino indicado, ya sea porque recibe información sobre cómo llegar hasta el siguiente punto (en el recomendador de turismo en Madrid) o porque puede consultar información extra sobre los puntos que visita (en el Museo García Santesmases). 5.2. Trabajo futuro Aunque se han cumplido los objetivos propuestos, este trabajo abre nuevas líneas de trabajo futuro. Se pretende extender el número de casos base utilizando un procedimiento de adquisición automática de casos, donde se almacenen los datos de las visitas del museo utilizando dispositivos de localización como beacons , que permiten detectar la posición del usuario. También se podrían estudiar otras medidas de similitud u otros métodos de adaptación más complejos. Así, se espera que la calidad de la solución (medida por la cobertura) se incremente al añadir más casos reales. Por otra parte, en el caso de visitas grupales, las preferencias de los usuarios introducidas en las consultas están calculadas como media de los miembros del grupo, lo que resulta en una tarea tediosa de descripción de la entrada. Una alternativa es usar una descripción aproximada de las preferencias del grupo basada en visitas prototípicas, lo cual es adecuado para reutilizar soluciones CBR. Los casos en el sistema CBR representan visitas reales, y los primeros experimentos con ellos mostraron que se puede simplicar la representación del mapa del museo donde todos los nodos están conectados a los demás: a pesar de que es teóricamente posible visitar un nodo después de cualquier otro, esto no ocurre en las visitas reales, pues en el camino a los nodos más lejanos, los usuarios siempre visitan nodos intermedios. Este conocimiento ha sido capturado observando los casos base y podría ser usado para simplicar el mapa agrupando diferentes objetos de cara a aplicar el algoritmo A ? . Respecto a las recomendaciones, sería interesante poder aplicar los conceptos del ltrado colaborativo. Tras realizar la ruta propuesta por el recomendador, los usuarios podrían valorar su grado de satisfacción con cada nodo visitado, y añadir esta información 56 Personalización de rutas en sistemas de turismo y ocio CAPÍTULO 5. CONCLUSIONES Y TRABAJO FUTURO al sistema para futuras consultas, pasando así de un sistema recomendador basado en contenido a uno híbrido. La parte de Realidad Aumentada en el Museo García Santesmases también podría ser mejorada, ampliando el número de vitrinas que ofrecen contenidos de Realidad Aumentada y mejorando la calidad de esos contenidos, incluyendo animaciones o sonidos. Además, se propuso una idea (desestimada por su alta complejidad) consistente en realizar un guía virtual que llevase al usuario a través del museo, parándose en las vitrinas seleccionadas por el recomendador y proporcionando información adicional a la mostrada en la propia vitrina. En el Recomendador en Madrid se podrían renar los contenidos de Realidad Aumentada, incluyendo más datos o interacción mediante botones virtuales. Para localizar al usuario dentro del museo y así poder guiarle también serían de utilidad los beacons o cualquier sistema de posicionamiento en interiores (IPS, en sus siglas en inglés). No obstante, la tecnología relativa a este campo todavía no está lo sucientemente avanzada como para que el error relativo al posicionamiento sea asumible, sobre todo al tratarse de museos con tan poco espacio entre sus vitrinas. Personalización de rutas en sistemas de turismo y ocio 57 Bibliografía [1] Yifeng Zeng y col. Optimal Route Search with the Coverage of Users' Preferences. En: Proceedings of the 24th International Joint Conference on Articial Intelligence (IJCAI 2015) . AAAI Press, 2015, págs. 2118-2124. isbn : 9781577357384. [2] Kenneth H. Rosen. Discrete Mathematics and Its Applications . 5th. McGraw-Hill Higher Education, 2002. isbn : 0072424346. [3] Stuart Russell y Peter Norvig. Articial Intelligence: A Modern Approach . 3rd. Upper Saddle River, NJ, USA: Prentice Hall Press, 2009. isbn : 0136042597. [4] G.F. Luger. Articial Intelligence: Structures and Strategies for Complex Problem Solving . Addison-Wesley, 2005. isbn : 9780321263186. url : https : / / books . google.co.uk/books?id=QcTuJb7Hi40C . [5] Elaine Rich y Kevin Knight. Articial Intelligence . 2nd. McGraw-Hill Higher Education, 1990. isbn : 0070522634. [6] Informed search algorithms . url : https : / / courses . cs . washington . edu / courses/csep573/11wi/lectures/03-hsearch.pdf . [7] Paul Resnick y Hal Varian. Recommender systems . Vol. 40. New York, NY, USA: ACM, 1997, págs. 56-58. [8] Robin Burke. The Adaptive Web. En: ed. por Peter Brusilovsky, Alfred Kobsa y Wolfgang Nejdl. Berlin, Heidelberg: Springer-Verlag, 2007. Cap. Hybrid Web Recommender Systems, págs. 377-408. isbn : 978-3-540-72078-2. url : http://dl. acm.org/citation.cfm?id=1768197.1768211 . [9] Francesco Ricci y col. Recommender Systems Handbook . 1st. New York, NY, USA: Springer-Verlag New York, Inc., 2010. isbn : 0387858199, 9780387858197. [10] Damianos Gavalas y col. Mobile recommender systems in tourism. En: Journal of Network and Computer Applications 39 (2014), págs. 319-333. [11] Robert Parviz Biuk-Aghai, Simon Fong y Yain-Whar Si. Design of a recommender system for mobile tourism multimedia selection. En: Internet Multimedia Services Architecture and Applications, 2008. IMSAA 2008. 2nd International Conference on . IEEE. 2008, págs. 1-6. [12] Liliana Ardissono y col. Intrigue: personalized recommendation of tourist attractions for desktop and hand held devices. En: Applied Articial Intelligence 17.8-9 (2003), págs. 687-714. Personalización de rutas en sistemas de turismo y ocio 59 APÉNDICE A. RELACIÓN DE OBJETOS DEL MUSEO GARCÍA SANTESMASES 6. IBM 7090 (1959) Primer computador comercial transistorizado Tiempo de visita: 1 minuto 45 segundos Etiquetas: FDI 0,3; Videojuegos 0,5; Cine 0,3 7. Cursos de automática de García Santesmases Tiempo de visita: 1 minuto 15 segundos Etiquetas: Docencia 0,6; España 0,4 8. Enseñanza asistida por computador Tiempo de visita: 2 minutos Etiquetas: Docencia 0,8; FDI 0,7; España 0,3; Historia 0,3 9. Calculadoras Tiempo de visita: 1 minuto 30 segundos Etiquetas: Cine 0,2; Ciencias 0,5 10. Friden EC-132 (1965) + Tubo de Rayos Catódicos Tiempo de visita: 30 segundos Etiquetas: Hardware 0,7; PCs 0,3; Ciencias 0,2 11. Calculadora de raíces cuadradas Tiempo de visita: 30 segundos Etiquetas: Curiosidad 0,6; Ciencias 0,3; Hardware 0,2 12. PDA's y tablets Tiempo de visita: 30 segundos Etiquetas: Ciencias 0,5 13. Periféricos de IBM Tiempo de visita: 30 segundos Etiquetas: Periféricos 0,7 14. Arte por computadora Tiempo de visita: 1 minuto 45 segundos Etiquetas: FDI 0,8; Arte 0,9; Ciencias 0,9 15. Unidades de cinta + Discos físicos Tiempo de visita: 45 segundos Etiquetas: Cine 0,7; Curiosidad 0,6 66 Personalización de rutas en sistemas de turismo y ocio APÉNDICE A. RELACIÓN DE OBJETOS DEL MUSEO GARCÍA SANTESMASES 16. Teléfonos Tiempo de visita: 1 minuto 45 segundos Etiquetas: Curiosidad 0,5; FDI 0,3 17. Sony AIBO ERS-7 (2003): Perro robótico Tiempo de visita: 1 minuto Etiquetas: Videojuegos 0,3; Curiosidad 0,3 18. PDP 11 Tiempo de visita: 1 minuto 45 segundos Etiquetas: FDI 0,3; Curiosidad 0,2; Redes 0,8 19. Ordenadores circa 1990 (Amstrad, Tulip, Tamdon, Toshiba) Tiempo de visita: 1 minuto Etiquetas: PCs 0,7; Curiosidad 0,3 20. Memorex 1337 + Fichas perforadas Tiempo de visita: 1 minuto 30 segundos Etiquetas: PCs 0,8; Historia 0,3; Curiosidad 0,4; Cine 0,2 21. Carteles Tiempo de visita: 1 minuto Etiquetas: Docencia 0,4 22. HP 21MX + Cinta de papel Tiempo de visita: 1 minuto Etiquetas: PCs 0,7; Redes 0,4; Cine 0,35 23. Simulador de centrales térmicas Tiempo de visita: 1 minuto 30 segundos Etiquetas: Curiosidad 0,7; Cine 0,4; Docencia 0,8; Periféricos 0,2 24. IBM-PC XT 1983 Tiempo de visita:1 minuto Etiquetas: PCs 0,8 25. Plotter HP9872C Tiempo de visita: 1 minuto Etiquetas: PCs 0,5 Personalización de rutas en sistemas de turismo y ocio 67 APÉNDICE A. RELACIÓN DE OBJETOS DEL MUSEO GARCÍA SANTESMASES 26. HP 9000/319 Tiempo de visita:1 minuto Etiquetas: PCs 0,65 27. HP 1000 (1982) Tiempo de visita: 1 minuto Etiquetas: Redes 0,7 28. Ordenadores Amstrad Tiempo de visita: 4 minutos Etiquetas: Videojuegos 0,95; Curiosidad 0,7; Arte 0,85; España 0,85; PCs 0,8 29. Consolas Atari y Nintendo Tiempo de visita: 3 minutos Etiquetas: Videojuegos 0,95; Curiosidad 0,7; FDI 0,6; Cine 0,5; Historia 0,3 30. Ordenadores Sony, Amstrad, ... Tiempo de visita: 1 minuto 30 segundos Etiquetas: Historia 0,4; Videojuegos 0,85; España 0,4; PCs 0,8 31. Máquina recreativa Tiempo de visita: 2 minutos 15 segundos Etiquetas: Curiosidad 0,5; Cine 0,7; Videojuegos 0,95 32. Cables Tiempo de visita: 1 minuto 15 segundos Etiquetas: FDI 0,4; Hardware 0,6 33. Procesadores de Intel Tiempo de visita: 1 minuto 15 segundos Etiquetas: FDI 0,4; Hardware 0,95 34. IBM 3097: refrigeración líquida Tiempo de visita: 2 minutos 15 segundos Etiquetas: Ciencias 0,8; Hardware 0,7 35. Disco duro 8 GB Tiempo de visita: 45 segundos Etiquetas: Almacenamiento 0,85 68 Personalización de rutas en sistemas de turismo y ocio APÉNDICE A. RELACIÓN DE OBJETOS DEL MUSEO GARCÍA SANTESMASES 36. Plato 6 MB Tiempo de visita: 1 minuto 30 segundos Etiquetas: Cine 0,5; Almacenamiento 0,95; Historia 0,2 37. Memorias de ferrita y otros dispositivos de almacenamiento Tiempo de visita: 1 minuto 15 segundos Etiquetas: Almacenamiento 0,8; Historia 0,3 38. Transistores, ROMs, circuitos integrados, obleas Tiempo de visita: 1 minuto 45 segundos Etiquetas: Hardware 0,95; Curiosidad 0,3; Almacenamiento 0,3 39. Periféricos y conectividad Tiempo de visita: 1 minuto 15 segundos Etiquetas: Redes 0,3; Cine 0,3; Periféricos 0,5 40. Disquetes 31/2 ; 51/4 Tiempo de visita: 1 minuto Etiquetas: Periféricos 0,9; Cine 0,2 41. Impresoras Tiempo de visita: 1 minuto Etiquetas: Periféricos 0,7 42. Periféricos: ratones, teclados, lápiz táctil Tiempo de visita: 1 minuto 15 segundos Etiquetas: Periféricos 0,8 43. Discos duros Tiempo de visita: 1 minuto Etiquetas: Almacenamiento 0,85 44. Discos duros antiguos Tiempo de visita: 1 minuto Etiquetas: Almacenamiento 0,9 45. PCs Tiempo de visita: 2 minutos 30 segundos Etiquetas: PCs 0,95; Historia 0,3; Videojuegos 0,35 Personalización de rutas en sistemas de turismo y ocio 69 APÉNDICE A. RELACIÓN DE OBJETOS DEL MUSEO GARCÍA SANTESMASES 46. IBM 5110 Computing System Tiempo de visita: 2 minutos Etiquetas: PCs 0,95; Periféricos 0,3 47. DEC AlphaServer 2100 Tiempo de visita: 1 minuto 15 segundos Etiquetas: Servidores 0,85; Redes 0,8 48. Ordenadores de Apple Tiempo de visita: 2 minutos Etiquetas: PCs 0,95; Cine 0,5; Curiosidad 0,5 49. Servidores Unix Tiempo de visita: 1 minuto 15 segundos Etiquetas: Servidores 0,9; Redes 0,8 50. Cray Y-MP EL (1991) Tiempo de visita: 2 minutos Etiquetas: Servidores 0,9; Hardware 0,6 51. Origin 2000 Tiempo de visita: 1 minuto Etiquetas: FDI 0,7; Servidores 0,8 52. Servidores actuales Tiempo de visita: 1 minuto Etiquetas: Servidores 0,9 70 Personalización de rutas en sistemas de turismo y ocio B Relación de puntos de interés en Madrid 1. Plaza Mayor Tiempo de visita: 30 minutos Etiquetas: Monumento 0,9; Historia 0,5 2. Puerta del Sol Tiempo de visita: 20 minutos Etiquetas: Historia 0,4; Monumento 0,8 3. Catedral de la Almudena Tiempo de visita: 40 minutos Etiquetas: Iglesia 0,95; Monumento 0,3; Arte 0,3 4. Chocolatería San Ginés Tiempo de visita: 40 minutos Etiquetas: Gastronomía 0,9; Infantil 0,3 5. Mercado de San Miguel Tiempo de visita: 1 hora Etiquetas: Gastronomía 0,8 6. Palacio Real Tiempo de visita: 1 hora 10 minutos Personalización de rutas en sistemas de turismo y ocio 71 APÉNDICE B. RELACIÓN DE PUNTOS DE INTERÉS EN MADRID Etiquetas: Historia 0,8; Cultura 0,7 7. Museo del Prado Tiempo de visita: 2 horas Etiquetas: Museo 0,9; Cultura 0,6; Arte 0,9 8. Barrio de La Latina Tiempo de visita: 1 hora 30 minutos Etiquetas: Gastronomía 0,6; Entretenimiento 0,6 9. Casa Museo del Ratón Pérez Tiempo de visita: 40 minutos Etiquetas: Infantil 0,95; Museo 0,4; Entretenimiento 0,4 10. Teatro Real Tiempo de visita: 1 hora 10 minutos Etiquetas: Cultura 0,8; Historia 0,4 11. Círculo de Bellas Artes Tiempo de visita: 30 minutos Etiquetas: Arte 0,9; Entretenimiento 0,2 12. Puerta de Alcalá Tiempo de visita: 15 minutos Etiquetas: Monumento 0,8 13. Parque de El Retiro Tiempo de visita: 2 horas Etiquetas: Entretenimiento 0,7; Infantil 0,2 14. Monasterio de las Descalzas Reales Tiempo de visita: 1 hora Etiquetas: Iglesia 0,7; Historia 0,4; Arte 0,5 72 Personalización de rutas en sistemas de turismo y ocio