Visiting Hybrid Museums: A Colony of Ants in your Pocket

by Javier Jaén and José A. Mocholí

Tangible and intangible digital objects in areas of cultural heritage are becoming increasingly interrelated. Intangible multimedia objects provide contextualization and additional information that aids in the understanding of artistic creative processes. These types of interrelated information must therefore be made available for museum visitors, so that they may have a more enriching experience. This note reports on our experience in the use of evolutionary algorithms based on ant colonies for the efficient provision of dynamic time-constrained visits in Hybrid Museums.

One of the most enriching and exciting experiences that differentiates human beings from other animals is our ability to use expressions of artistic or cultural work to stimulate our senses and to experience a range of emotions. As a result, in the cultural domain, there is a mandate to save not only the artistic expressions from earlier times, but also the commentaries, reflections and knowledge relationships relating to these expressions. In this way, we avoid dangers such as forgetting the past and destroying memory.

In this respect, digital culture must face a number of challenges in the coming decades. First, it must provide adequate multimedia expressions for both tangible and intangible heritage. Second, these new multimedia and multimodal forms of culture must be properly conserved and preserved. Third, both tangible and intangible cultural expressions must be properly interrelated with respect to different awareness contexts or dimensions. Lastly, the resulting vast amount of distributed and interrelated cultural information must be properly delivered to the end users. This should be done with simple navigation or exploration mechanisms that are intuitive and hide the inherent complexity of the different forms of interrelated heritage.

The MoMo project, a collaboration between the Polytechnic University of Valencia in Spain and the Microsoft Research Labs (Cambridge), is a step towards solving these challenges in the context of hybrid museums (HMs). HMs are known as infrastructures that enable the exploration of traditional museums with the assistance of wireless Personal Digital Assistants (PDAs) that have multimedia capabilities and are able to adapt dynamically to visitors' preferences and behaviour. However, as the number of cultural elements and amount of interrelated information grows, visitors need some form of automatic assistance in deciding how to visit as many popular artworks (those belonging to the most relevant artists) as possible within their available time.

This problem, which has traditionally been known as the Orienteering Problem (OP), is a combinatorial problem that cannot be solved in polynomial time. Moreover, in the case of museums where nodes in the OP graph are artworks, the sizes of typical OP instances are in the thousands of nodes. Therefore, solving such instances with exact algorithms is not a feasible approach. Instead, mechanisms based on heuristics are more suitable. In particular, our research makes use of evolutionary algorithms inspired by the natural behaviour of ant colonies to provide efficient and high-quality solutions to this problem. Ant colonies are insect societies that accomplish complex tasks by presenting highly structured organizations and communication mechanisms. Ant behaviour is based on the use of pheromones, and in particular the trail pheromone. This chemical is used to mark paths on the ground from food sources to the nest. Several experiments have shown that this communication mechanism is very effective in finding the shortest paths and as a result, has inspired several stochastic models that describe the dynamics of these colonies.

Ant Colonies optimization algorithms are effective heuristics for solving problems of medium size (hundreds of nodes). However, the computational cost when dealing with the thousands of nodes of a museum is prohibitive, because visitors are not willing to wait several minutes (even half an hour) to obtain a reasonable solution. Instead, our strategy has been to solve large OP instances with thousands of nodes by partitioning the search space into subspaces and then solving the subproblems. This is done with the help of a Grid computing infrastructure with no communication for synchronization purposes among the worker nodes of the infrastructure. Our mechanism can be seen as a master-slave approach like that proposed by Middendorf, but with no pheromone matrix propagation because the slaves work on independent instances.

Figure 1: Ant Colony solution at El Prado Museum. Figure 2: MoMo's Graphical User Interface.

The results we have obtained prove that instances of this problem of up to several thousand elements can be solved within a few seconds. Moreover, because we have implemented this distributed infrastructure with the .NET technology, not only desktop PCs but also the handheld devices that are present in the HM can host ant colonies. Figure 1 shows an example of a computation obtained for El Prado museum, where the red rooms are the most attractive ones and the blue ones are the least. It can be observed that the collective effort of ants obtains a path that visits most of the popular rooms within the specified available time.

This evolutionary approach, together with some additional intelligent prediction components, contributes to more exciting and enriching museum experiences and could be the foundation for museums that provide more effective guidance to visitors in the near future.

Links:
http://momo02.dsic.upv.es
http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html
http://research.microsoft.com/aboutmsr/labs/cambridge/default.aspx

Please contact:
Javier Jaén, Universidad Politécnica de Valencia / SpaRCIM
E-mail: fjaendsic.upv.es
http://issi.dsic.upv.es/Members/plone/Members/profes/fjaen