The problem

Ask yourself about what you would be doing if you just have one hour and a half to spend at Le Louvre? Our purpose is to help a visitor finding a “good answer” to such a question.

This problem is a novel application. The need for personalized visits comes from the fact that for a large number of museums, it is not conceivable to spend time in front of every art piece, especially because of their number which can be huge (exceeding thousands of items in some museums). This is why it makes sense to prepare a visit.

We have developed an approach to solve this problem. The approach is detailed in an article that will be presented at the 23rd Conference on International on Automated Planning and Scheduling (ICAPS'13) in June 2013.

Download preprint paper

Benchmarks

No benchmarks for the museum visits problem are currently available. To test our approach, we have created two sets of benchmarks. We have considered two museums: a small one, the “Palais des Beaux Arts de Lille” , and a much bigger one, the “National Gallery” of London.

Characteristics of museums is presented in the table below.

Museum	Rooms	Alleys	Entrance	Exit	Artworks
Palais des Beaux Arts	53	121	1	1	486
National Gallery	119	304	4	4	1783

We used those two museums to test our encoding scheme of the shortest complete walk problem. For this problem, the input is the museum graph as presented in Section 2. Starting with the floor plans available on museum websites, we used the dot language Graphviz to represent the museum topology.

• 

  Palais des Beaux Arts

• 

  National Gallery

We enriched dot files representing the topology of each museum with the different elements needed for the museum visit instances, i.e., the artworks information, the maximum time bound and the length of the shortest complete walk. Many visitors profiles can be envisioned, associated with many different utility distributions.We considered three distribution types, which differ according to the balance ability they offer. The first one, unif, corresponds to users with weak preferences on art pieces (i.e., utility compensations are often feasible). To be more precise, a random integer between 0 and 1000 is associated to each artwork following a uniform distribution. The second utility profile (fibo) corresponds to users with mild preferences. We consider 20 utility levels and the utility values for these levels match the first integers of Fibonacci sequence. The artworks number for each of these levels is the same one. Finally, the third profile (luby) corresponds to users with marked preferences on art pieces. It is based on a Luby sequence as presented in (Luby, Sinclair, and Zuckerman 1993). The higher the level, the fewer the number of artworks.

In order to generate a wide family of profiles, we fixed the percentage of artworks that do not interest the visitor at all (null) and the percentage of artworks that the visitor considers being the most interesting ones (master). Independently of the function used to define the visitor satisfaction, noninteresting artworks are attributed a null utility and the most interesting artworks are given the maximum utility value. We used the same percentages 0, 10, 20 and 50 for both kinds of artwork, leading to 16 different combinations.

Another parameter to be made precise is the time the visitor is willing to spend in front of each artwork. This time depends on the utility given to an artwork: it seems reasonable to spend more time in front of a very interesting art piece and less time in front of a less interesting one. Nevertheless, this time cannot be null. We consider two cases. In the first case, times to spend in front of artworks and times to go from one room to another are approximately the same. In the second case, times to spend in front of artworks are twice as long as times to go from a room to an adjacent room in the museum. The objective is to observe the impact of different visit rhythms on the behavior of the solvers.

Benchmarks have been generated from dot files using two approaches. The first approach is constraint-based : resulting benchmarks are in opb format. The second approach is a planning approach and resulting benchmarks are in pddl format.

 Download benchmarks in dot format Download benchmarks in opb format Download benchmarks in pddl format

PMV Solver

PMV is a dedicated solver based on Sat4j. First experiments showed that LPG gave very good results. We assumed that it was because LPG was looking for solutions with increasing plan length. PMV solves the museum visits problem with increasing steps k using a quick timeout, until the bound is reached. We used a timeout of 5 seconds for the first 10 steps, 20 seconds for the following 10 steps and finally 80 seconds per remaining step. That increasing timeout is made to adapt the solver to the increasing search space. The solver also has a timeout for optimizing the solution found, equals to 1/5 of the global timeout.

Download PMV

Detailed Results

All results have been reported in the following worksheet.

Download results

Tech-A-Way

Tech-A-Way is a prototype in which previous results are implemented. Such a tool is designed to be accessible from a museum web site or from a born at the entrance of a museum. As it can be seen on the following video, the tool is composed of different screens that allow the visitor to express her constraints and preferences about a visit. For this prototype, a database of 1800 artworks has been created. Topology looks like the Louvre-Lens one with one big room (the Time Gallery). It has been developed by S. Roussel.

Contacts

The paper has been written by P. Marquis, D. Le Berre and S. Roussel.

Tech-A-Way prototype has been developed by S. Roussel.