1 Cultural property – heritage and responsibility

The individuals that form a people, a nation or state very often identify themselves with their country, their language, history and culture. Culture can – in the form of cultural property such as monuments, buildings, works of art, and collections – be made conspicuous and thus visible, touchable and comprehensible. The safeguarding of this cultural property is of immensurable significance, since it builds identity and is therefore of existential importance.

A country’s cultural heritage is indeed a growing, yet not a renewable, resource. When cultural property is destroyed, its loss is fundamentally irrevocable, aside from the possibility of the reconstruction of destroyed items. In order to prevent severe damage or even total loss existing damage has to be eliminated, and future damage has to be prevented. In order to justify the financial effort of research and implementation within this context, national economics have to be taken into account.

The destruction of cultural property in the event of armed conflict, the looting of cultural sites from antiquity, innumerable illicit excavations at archaeologically important sites as well as the mass theft of objects of art all over the world – from sacred places, museums, archives, libraries and other institutions which accommodate cultural property – pose a threat to scientific analysis, conservation and public access to our common cultural heritage.

The revenue resulting from illegal trafficking of cultural property goes into the billions of Euros and has reached the dimensions of the illegal trafficking of weapons, drugs, humans and endangered animal species. The damage resulting from it is immeasurable. Since the looting of cultural sites and the illegal trafficking of cultural property are aspects of organised crime and since the proceeds of illegal trade add to the income of international terror organizations, the efficient protection of cultural property is also a question of public security.

In addition, natural disasters and economic progress still pose a profound threat to cultural property. Earthquakes, floods, fires and other catastrophes time and again damage or destroy cultural sites of the first rank. In the minds of corporate leaders and political decision-makers, economic progress – which goes mostly hand in hand with expansive construction industries – still seems to be incompatible with the interests of a modern way of protecting cultural property.

At the same time, in most countries cultural property is protected by national and international laws in peacetime as well as in the event of armed conflict. However, laws are in many cases insufficiently applied, or not at all, and sometimes even conventions remain unratified. The reality of the protection and safeguarding of our cultural heritage unfortunately looks rather gloomy. Urgently needed preventive measures for the protection of cultural property are all too often not taken, mostly under the pretence of financial reasons.

The requirement for modern and more effective protection of cultural property is gaining more and more importance in our society because of the recent armed conflicts in Afghanistan or in Iraq, in Kosovo or Bosnia-Herzegovina, in the Gaza strip or in the Lebanon, in Sri Lanka or in East Timor and many other crisis areas. Media coverage of the topic is constantly increasing, allocating a lot of importance to the looting and destruction of cultural property. The media reports of the looting of the Iraq Museum thus turned the initial military success of the US forces during the operation ‘Iraqi Freedom’ in the spring of 2003 into a moral defeat for the USA, turning cultural property protection into a political issue. In inter-ethnic conflicts the destruction of the enemy’s cultural property is often part of the strategy, which in the end makes a sustainable peace process more difficult. The protection of cultural property is not only an issue in classical war scenarios but has to be taken into account in any kind of military operation, including UN peacekeeping operations and multinational stability operations. The protection of particularly endangered cultural property has to be integrated into the budgeting of military operational planning in any case, because afterwards no financial means for this fundamental element of Civil-Military Cooperation (CIMIC) will be made available. It is of course also essential that the local population realise the value of their cultural property and care for it themselves. It is a fact that the protection of cultural property is not possible in the long run without the commitment of the local population.

It must not be forgotten however, that the intended destruction of an enemy’s cultural property as a type of ‘warfare by other means’ has probably always been a side effect of conflicts and may also be an aspect of ethnic cleansing. The massive destruction of cultural property during the armed conflicts in the Balkans between 1990 and 1998 is a prominent example from our most recent history.

Natural catastrophes, such as tsunamis or floods, have also severely damaged or destroyed cultural property in the past few years including the destruction of a number of important historical Saxon centres in the course of the serious flooding in Eastern Germany, the Czech Republic and Northern Austria in 2002, and the tsunami that ravaged vast parts of Indonesia, Sri Lanka, Thailand and India during the Christmas of 2004. There were also vast fires, which for example severely damaged the Hofburg Palace in Vienna in 1992, and the Duchess Anna Amalia Library in Weimar in 2004. In particular the recent entry of rainwater into the ultramodern depots of the Albertina gallery in Vienna in 2009, with a total failure of the automatic rescue measures is a prime example of the current inadequate measures in the area of cultural property protection.

All of these cultural catastrophes quickly found their way into the international headlines. Through such experiences the problem of Protection of Cultural Property (PCP) became known to political decision makers. It must no longer be tolerated that a particular cultural property is afflicted and damaged time and again by the recurrence of the same natural disaster (such as flooding) and no protective measures are taken that prevent further damage or even the destruction of it. Be it a threat posed by human or natural processes, the protection of cultural property cannot be achieved by a laissez-faire attitude, not least because of legal demands. PCP measures cost money and require political and public will to take the necessary financial measures. In the end the responsibility lies with civil society to demand the measures needed of the political leaders and public authorities, and non-governmental organizations also play an important role.

2 Sheltering moveable cultural property

2.1 Moveable cultural property and shelter rooms

We basically distinguish between moveable and immoveable cultural property. The latter cannot be moved in dangerous situations and can therefore not be taken to safe places. This kind of property has to be protected on the spot as well as possible. Movable objects can be disassembled in a short time or moved to a shelter in one piece, for example works of art, manuscripts, books and other objects of artistic, historical or archaeological interest as well as scientific collections and collections of reproductions of cultural property.

However, it is unfortunately common practice that shelter room are insufficiently filled, by making use of approximately 25% of the available volume only, with the other 75% of the room unused. Appropriate protection measures for cultural property have to be taken by law, but because of the high costs these obligations are often only partly put into practice, and cultural property is left to possible destruction.

Research of the latest technologies can help to develop standards which safeguard the proper storage of moveable cultural property. The aim of this research is to develop shelter rooms for this purpose.

A new standard for the optimisation of sizes and therefore for the financing of shelter rooms is established. The size of the room is to depend on the number and the size of the items of moveable cultural property in a particular facility. The use of space is to be maximised by an optimal stacking of the crates containing the property. As a result of this cost reduction it will be easier for the institutions in the possession of cultural property to build and run the necessary shelter rooms, which in turn contributes to the survival of valuable, irretrievable objects.

2.2 Legal basis for shelter rooms in international law

PCP is basically a task of its own for every sovereign state, and measures for the protection of cultural property are a matter of national legislation. There is also international legislation for the protection of cultural property in addition to this, which is however, only useful when the respective state has ratified the convention. While the Convention for the Protection of World Cultural and Natural Heritage (Paris, 1970) remains rather unspecific regarding concrete protective measures, the Convention for the Protection of Cultural Property in the Event of Armed Conflict (The Hague, 1954) is relatively concrete:

Chapter 1: General Provisions Regarding Protection, Article 4: Respect for cultural property

1. The High Contracting Parties undertake to respect cultural property situated within their own territory as well as within the territory of other High Contracting Parties by refraining from any use of the property and its immediate surroundings or of the appliances in use for its protection for purposes which are likely to expose it to destruction or damage in the event of armed conflict; and by refraining from any act of hostility directed against such property.

The Second Protocol to this Convention (The Hague, 1999) contains further specific provisions:

Chapter 2: General Provisions Regarding Protection, Article 5: Safeguarding of Cultural Property

Preparatory measures taken in time of peace for the safeguarding of cultural property against the foreseeable effects of an armed conflict pursuant to Article 3 of the Convention shall include, as appropriate, the preparation of inventories, the planning of emergency measures for protection against fire or structural collapse, the preparation for the removal of movable cultural property or the provision for adequate in situ protection of such property, and the designation of competent authorities responsible for the safeguarding of cultural property.

From this it can be legally deduced that there have to be places for moveable cultural property in states that are parties to the Convention where cultural property can be safely stored. Timely preparation for the movement of tangible cultural property has to be planned in times, when such property is not yet in danger. The preparation of adequate protection of this property on site is also part of this.

2.3 Construction standards for shelters of cultural property

The dimensions of the shelter room are prescribed by framework conditions. These can be for instance the prescription of the protection degree “bunker” against bombs or rocket fire, which results in a possible static ceiling span on the one hand, or of the requirements for filling on the other, which can be done either only by the use of manpower (ceiling height up to approx. 2.20 m) or with fork lifts (ceiling height up to approx. 8.00 m).

In order to ensure the best possible protection a standard for a shelter room is drawn up according to the following parameters:

• protection against weapon effects (shock, radiation)
• protection against water
• development of adjusted environmental conditions in the shelter
• location near the moveable cultural property
• appropriate fire control
• development of filling times (evacuation plan)
• development of a construction standard (shock safety, no use of dangerous materials)
  
  

Fig. 1: Picture of a possible shelter room for cultural property (Bundesamt für Zivilschutz, Int. PCP meeting, Bern 2002)

The following criteria for the acceptance of PCP objects apply:

• material
• climate
• dimensions
• static
• place
• packaging

2.4 Filling of a shelter room

Fig. 2: Filling a shelter room in three steps

It is important for the objects not to touch the ground directly and to have small interim spaces between them so that ventilation is ensured. In order to prevent the containers from tilting placeholders are inserted if needed.

3 Developing a new dimension standard

3.1 Shelter room and cost reduction

Currently many stakeholders of cultural property object to their legal obligation by pointing out the problem of excessive costs, and therefore either do not protect the irretrievable cultural property at all, or at best inadequately. With the development of a minimum requirement involving efficient filling, the costs can be reduced drastically and the argument that they are impossible to finance is made obsolete.

3.2 An ant colony system for the knapsack problem

A possible solution is the ant colony system (ACS), a variant of the well known knapsack problem. For a fixed number of square objects every agent (in this case an ant) produces a sequence and a list of orientations for the objects. With the help of a simple constructive heuristic (approximation procedure) they are arranged in the three-dimensional space. Heuristics are based on the idea that rather good solutions can often be found with a relatively small calculation effort. Exact procedures in comparison take so much time that the increase in quality achieved by them is no longer justified or the solution is no longer needed. The focus lies with a secure identification of high-quality solutions under the consideration of realistic side conditions concerning the placement of the objects.

3.3 Advantages of the ant colony system

According to Bortfeldt (2006), the type of metaheuristic does not seem to be as important as the integrated heuristic (in this case a constructive heuristic) but Ant Colony Optimizaton (ACO) may score on the author’s demand for an efficient control of the search through metaheuristic. As compared to other metaheuristics like Simulated Annealing (SA) or Genetic Algorithms (GA) this is a strong side of the ACO (see Schreyer and Raidl, 2002; Levine and Ducatelle, 2004).

A good approach is to test the constructive heuristic with a fast and simple to implement SA-approach at first. The result is an improved constructive heuristic and a first impression of the performance gain of a metaheuristic. On this basis a decision for a GA or ACO can be made. The latter brings better results in general but needs more fine-tuning when there are a higher number of parameters. However, Gutjahr (2002) describes a promising approach for the automatic adaptation of some parameters that can decisively alleviate this downside. According to Dorgio (2003), ACOs have a lot of potential for problems which are hard to structure or for which no efficient local optimisation is possible.

3.4 Advantages of constructive heuristic

This heuristic involves automatic stacking:

By sorting possible positions for the objects in list C (see section 3.7: A constructive heuristic), a real stacking process is copied, which means that objects always stand on the ground or on top of other objects.

The representation of the objects can be used for boundary conditions:

In the heuristic, objects take up space. By emulating the container-space within the heuristic, overhanging objects for example can be easily avoided, because the surfaces are already known (for example when the height of objects is increased with a “phantom object”, with a maximum height of the placeholders).

Modular use of algorithms:

The use of a sequence of objects as an interface between the constructive heuristic and the ant colony system detaches the two components from each other and thus produces flexibility when different techniques are applied. The ACO therefore doesn’t have to take care of the problem’s special features, and constructive heuristic can still be integrated into another metaheuristic instead of an ACO, just as in GAs or SAs.

The representation of the solution can be used for boundary conditions:

The positioning of objects based on the sequence leaves space for further boundary conditions through a change in the sequence. When compared to the global optimisation of the ACO this corresponds with a heuristic local search (combinational optimisation is usually a search), because the problem is considered part by part rather than as a whole. For example, heavy objects can be placed first in the sequence to ensure they are always on the floor, by producing a sequence of heavy objects first and adding a sequence of lighter objects to them. The heuristic first processes heavy objects, which are only allowed to be positioned on the floor, and afterwards lighter objects, which can take any position.

3.5 Disadvantages of exact procedures

There is still hardly any practical use for exact algorithms such as Branch and Bound and the Simplex Procedure. The 3D versions of strip-packing or the knapsack system are NP complete and therefore cannot be solved for realistic problem instances in reasonable time. In a comparative study, Bekrar et al. (2007) show several exact procedures (among others a Branch and Bound approach) for 2D strip-packing, for which a Pentium M with 1.7 Ghz requires on average 163.34 seconds to calculate for ten elements, and for 25 elements as many as 2,282.28 seconds (38 minutes). For the Simplex Procedure the combinatorial complexity alone (here: the worst-case calculation) is 2n for problems with n elements (Greenberg, 1997). The Lagrange Formalism is no solution process on its own. It is used, among others, to soften the stringent demands of mathematical optimisation procedures. One of the stringent demands can thus be replaced by a less stringent demand, which can be handled more easily. With this so-called relaxation technique a combinatorial problem can be replaced by a less complex problem.

3.6 The statement of the knapsack problem

In the knapsack problem a knapsack has to be filled in the most optimal way. Here one can choose from a number of objects of different weight. The aim is to find the number of objects which can fill the knapsack as closely as possible to its maximum weight without exceeding it.

Fig. 3: A Knapsack Problem

Figure 3 shows a possible problem. When you put the 4kg object into the sack, you get a good solution (a better one than when taking the 3 kg object, but still not the best). It is often practical to depict a solution by a series (permutation), because the algorithms can be configured more easily.

Figure 4 shows several sequences which all give best-possible solutions, since they fill the sack, when the objects in front (red) are put into the knapsack.

Fig. 4: Possible solutions

The following is a variant of the knapsack problem. A fixed number of n differently formed cubical objects with the numbers i = 1, 2, …, n have to be placed as compactly as possible in a three-dimensional space, and the objects can sometimes be rotated. The cubical shelter room for is either open in one direction or very big. This direction is simply called T-direction; concerning the depth or longest side of the shelter room (see figure 5).

Fig. 5: Dimensions of the shelter room

The width and height of the shelter room result from the static necessity and from the way it is filled with cultural objects.

As above, solutions are shown as a sequence of all cultural objects, every object, however, has an additional orientation in space.

A solution therefore consists of two lists: a permutation (sequence) P = {p1, p2, …pn} of the objects, and a list R = {r1, r2, …r6} of the space orientation for every object. In the three-dimensional space there are six possibilities for each object (see figure 6).

For five objects for instance, with the numbers i = 0, 1, 2, 3, 4 P can be P = {3, 0, 2, 4, 1}. R (space orientation) can be defined as follows: R = {rH, rUR, rUR, rB, rHT}. Object 3 is the first in the series P and has the orientation rH. The objects 0 and 2 have their original orientation rUR.

In comparison to the knapsack problem a good arrangement in space always places all objects in the shelter room, with a small extension in the T–direction, and fulfils the restrictions (framework conditions) for the placement of the objects. This problem can be applied in PCP, where a shelter room of a minimal size shall be found for a defined number of objects.

Fig. 6: Possible solutions

Fig. 7: Sequence and orientation of objects

Realistic assumptions suggest a number of restrictions concerning the placement of objects. For comparatively complex problems metaheuristic approaches such as the ACS are often successful. Raidl and Kodydek (1998) have applied genetic algorithms to the Multi-Container-Packing-Problem. Ji et al. (2007) have described an ant colony algorithm for very big problem instances of the multidimensional knapsack problem. Dorigo (2003) concludes that ant colony systems offer enormous advantages for applications for which the local optimisation is hard to define or has unclear effects. Single ants are not very bright, but ant colonies are (Stanford University, 1993). An ant colony finds solutions to problems which are unreachable for single ants. Ants are helpless as individuals, but as a colony, however, they react efficiently to their environment. This is called collective intelligence, where simple living beings follow simple rules. No ant has an overview, none tells the other what to do, no leadership is necessary. An ant colony system lets thousands of software ants swarm out and find out where the pheromone traces for compact object positions for a shelter room are to be found.

A pictorial example of an ant colony system functions as follows. The aim of the example colony is, among others, to find the shortest way to a food source. On one single day every ant finds such a path by wandering around in its territory. In doing so it marks its way with pheromones by leaving these traces on the floor. In the evening, when all solutions (paths) have been finished, the ant that has found the shortest way is rewarded, in that it is allowed to mark the path it has found particularly intensely. On the following day one part of the ants will wander near the strongly marked path with a higher probability than before because one ant does not always decide alone at a crossroads, instead sometimes orientating with the good decisions made by other ants during the last few days (indirect communication). In the weeks after the first detection of the food source there are still many different paths there, which the ants follow in approximately equal measure.

Fig. 8: Pictorial example of an ant colony system, first detection of food source

After some time the paths start to become shorter:

Fig. 9: Pictorial example of an ant colony system, shortest paths becoming established

And after a certain point in time, most ants will use a few of the shortest paths:

Fig. 10: Pictorial example of an ant colony system, shortest paths now established

This ant colony system consists of several parts which are described below. With a constructive heuristic and the target function an ant can assess how good its solution is. A constructive heuristic builds a descriptive and assessable picture from the originally abstract solution (the two lists P and R described above). The target function now assesses how well this picture meets the target of the problem by expressing the quality of the solution by some sort of measure.

An ant has a number of rules at its disposal, which it can use for deciding on which way to take. These rules also determine in which way the ant (indirectly) communicates with its colleagues. In short, they don’t represent a single ant’s intelligence. During its movement through the solution space (the colony’s territory) an ant produces a solution. It takes decisions about its way with the help of a pseudo-incident-proportional function, which constitutes half of the rules. The other part is the the local pheromone-update, which controls the indirect communication with other ants.

The colony consists of a number of ants and a pheromone memory (pheromone matrix), which saves the paths of all ants for a certain time. It serves both the indirect communication between ants and also their direct communication, when the best ant of the day is allowed to mark its solution again more strongly with the global pheromone update. Furthermore, the colony defines the ants’ daily procedure, since their lives are organised in days (iterations). In the morning, production of all solutions starts, and in the evening the finished solutions are assessed and the best ant of the day is rewarded.

3.7 A constructive heuristic

The Travelling Salesman Problem (Constructive heuristics construct new tours while optimising heuristics only optimise existing tours.)

It is the task of the simple constructive heuristic to place the number of given objects in space to achieve a valid solution. An ant gives the solution (that is the sequence and the objects’ orientation in space) and checks the quality of its solution with the aid of a constructive heuristic and the target function. The space to be filled, Z = (H, B, T) is defined with height and width, the depth is still unknown. It is simpler to take the depth as very big (see figure 5). Starting with a permutation of the series of objects pi and its orientation in space ri the algorithm functions as follows:

A list C with coordinates of possible positions for the objects is initialised: C = {c0} with c0 = (0, 0, 0) coordinate. This is the first point where an object can be placed (see figure 11).

Fig. 11: Initial point at which an object can be placed

All objects i are turned in a given order pi and spatial orientation ri and are placed in the space Z in the order given by P.

Fig. 12: Ordering and orientation of objects

The first object p0 has been positioned at position c0. This position is now filled and can be removed from C because no further object can be placed at this position:

Fig. 13: Position filled by object

By position c0 and the size of object p0 new possible positions c1, c2 and c3 are defined for other objects. They are sorted into C according to their priority, C = {c1, c2, c3}. The constructive heuristic has the capacity to produce formations which have a rather small depth and use the width and height of the space Z. This is ensured by the correct sorting of the positions, because then placing objects at positions of small depth is always attempted. The sorting into C happens as follows: c1 and c2 have a smaller depth than c3 and therefore c3 is placed at the very back: In addition, c1 has a smaller height than c2, and therefore c1 goes before c2. This way the objects are first ordered along the width of the space; if there is no space left, they are ordered along the height, and finally along the depth.

Fig. 14: Ordering of objects

Figure 14 shows the next iteration. At position c1 there is enough space for the second object p1. Position c1 is taken out of C, and the possible new positions c4 and c5 are sorted: C = {c4, c5, c2, c3}.

Fig. 15: Docking of objects

At positions like cx there were never any objects, they are neighbours of used positions and are, so to say, occupied by strange objects:

Fig. 16: Availability of docking points

The object px cannot be entered at one of the vacant positions in its given orientation, and so a new artificial position ck is produced, at which the object can be safely placed.

3.8 Target function and framework conditions

As the quality measure for the assessment of a solution, the extension Tmax of the sorted objects in the open direction T of the shelter room is used (see figure 17). The space is used efficiently, when all objects are placed but the extension in the open direction is small.

A number of restrictions also have to be born in mind. Apart from the following even more conditions are conceivable:

• Heavy objects like statues may only be placed on the floor.
• There are objects with restrictions as to their orientation. Paintings, for instance, may only be stored vertically.
• Objects that are not placed on the floor are not allowed to hang in the air.
  
  

Fig. 17: Quality assessment of solutions

The conditions are observed as much as possible as early as when the solution is being built in order to reduce the solution space. Fewer possibilities make it easier to find a solution. A restriction of the orientation can be defined by markers in the pheromone matrix (representing the ants’ common view of the solution space, or the set of all solutions) that cannot be exceeded. The points that are thus marked in a solution space will never be part of a solution.

By representing of the solution as a sequence of objects, the respective placement of heavy objects can only become apparent after the solution is built. For the fulfilment of this condition either a heuristic can be used by changing the sequence and placing such objects correctly, or the objective function does so by negatively assessing the solutions with unfavourably placed objects.

4 Summary

Both history and daily events demonstrate that cultural property has to be protected by suitable measures. The dangers are very real and of a wide range of kinds, including natural disasters as well as armed conflicts and technical weaknesses. However, the financial expenditure for shelters seldom matches the value – mostly hard to estimate – of cultural heritage.

In this context a more efficient use of shelter rooms (as far as space is concerned) seems highly attractive as a cost-saving alternative to extensions and new buildings, although new building standards and new software solutions are necessary. The problems that occur when a shelter is being filled with objects are being intensely researched with computer technology, whereby approaches to solutions for similar tasks have already produced good results.

The protection of cultural property can be made much more financially efficient – with the help of suitable standards and technical methods.

References

Bekrar, A, I Kacem and C Chu 2007 A comparative study of exact algorithms for the two dimensional strip packing problem. Journal of Industrial and Systems Engineering 1(2):151-170.

Bortfeldt, A 2006 A genetic algorithm for the two-dimensional strip-packing problem. European Journal of Operational Research 172(3):814-837, doi:10.1016/j.ejor.2004.11.016.

Dorigo M and T Stützle 2003 The ant colony optimization metaheuristic: algorithms, applications, and advances. Handbook of metaheuristics, Springer, pp. 250-285.

Greenberg, H J 1997 Klee-minty polytope shows exponential time complexity of simplex method. University of Colorado Press, Denver.

Gutjahr W J 2002 ACO Algorithms with Guaranteed Convergence to the Optimal Solution. Information Processing Letters 82:145-153, doi:10.1016/S0020-0190(01)00258-7.

Ji, J, Z Huang, C Liu, X Liu and N Zhong 2007 An ant colony optimization algorithm for solving the multidimensional knapsack problems, Intelligent Agent Technology, IEEE / WIC / ACM International Conference, Vol. 0, IEEE Computer Society, pp. 10-16.

Levine, J and F Ducatelle 2004 Ant colony optimisation and local search for bin packing and cutting stock problems. Journal of the Operational Research Society 55:705-716, doi:10.1057/palgrave.jors.2601771.

Raidl, G R and G Kodydek 1998 Genetic algorithms for the multiple container packing problem, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, Lecture Notes In Computer Science 1498:875-884.

Schreyer, M and G R Raidl 2002 Letting ants labeling point features, Proceedings of the Evolutionary Computation CEC 2002 Vol. 2, pp. 1564-1569.

Stanford University 1993 News Release, Stanford University, Stanford, California.