Qualitative Representation   Qualitative stability checking

## Qualitative stability checking   (written by Michał Zawidzki)

Qualitative stability checking is one of the problems analyzed within Qualitative Physics. The algorithms dealing with qualitative stability checking can be distinguished into two types: statically (kinamatically) and dynamically oriented. In the former what is investigated is the stability of a static scene, in the latter it is checked whether a construction remains stable after a force acts upon it.

In (Siskind 2000), (Siskind 2004) Siskind proposes a framework for kinematic analysis of stability of a two-dimensional scene composed of pentagonal blocks. He distinguishes lines that are "grounded" and then performs reasoning that answers if the whole scene is stable, whereas a scene is said to be stable if it is "immovable", i.e., cannot be moved. In Siskind's approach the reasoning is conducted for line segments, therefore polygons are represented by closed polylines. In such a scene representation some line segments intersect. Such an intersection point is called a joint. Siskind distinguishes three types of joints: revolute - if the angle between two constituent segments can change, prismatic - if it can "slide" along one of the constituent segments and rigid - otherwise. In Siskind's method each line segment should be ascribed two numerical values representing its linear and angular velocity. A number of conditions are formulated that determine how these values should be assigned to segments if they have a common joint. The key step of Siskind's method is answering the question of whether it is possible to achieve an assignment such that it preserves certain conditions (namely such that the entropy variable introduced to the scheme can be equated to zero). If such an assignment is feasible, it means that the whole scene is movable, i.e., unstable. In other words, the algorithm investigates whether the assumption that blocks constituting the scene move is consistent, and if the answer is affirmative, it claims instability of the investigated scene. Therefore, the whole problem of stability is here reduced to solving a set of linear equations and inequalities. Ultimately, Siskind's method provides us with a yes-no answer to the question of whether a scene is stable.

In (Blum et al. 1970) Blum et al. analyse the notion of stability within the dynamics paradigm. The motivation of their work is to verify whether a robotic arm programmed to erect a given block construction can add subsequent blocks to the structure without losing its stability. A two-dimensional variant of the problem is investigated. The method consists in analysing forces that act on particular adjacency points between blocks. Each such force occurs as a variable in a set of linear equations. Assuming that the masses of objects are known, also numbers occur in these equations. As Blum et al. show, the whole construction remains stable iff there exists a solution to the abovementioned set of equations in which all forces have non-negative values.

A qualitative stability analysis is delivered by Renz and Zhang in (Zang & Renz 2013) and extended in (Zang & Renz 2014). In their approach an object is said to be not stable if it will move (fall) under the influence of gravity. When an object is supported appropriately, it is stable. Their definition of stable objects involves a number of rules, where the most important one seems to be the one stating that "an object is stable and will not topple if the vertical projection of the centre of mass of an object falls into the area of support base". The authors of the paper notice that the provided rules do not exhaust all cases of blocks that remain stable, which is the result of the fact that they do not take into account objects lying on the block in question, even though they could play some role in preserving stability of this block. This is caused by the fact that reasoning about supporting blocks and their influence on the object's stability only requires qualitative categories introduced by ERA, whereas if blocks lying on the object are to be taken into account some numerical calculations would need to get involved, thus squandering the qualitative character of the whole method. Therefore it can be said that their method for reasoning about stability is sound but incomplete.

In (Wałęga et al. 2016) Wałęga et al. introduce another method of analyzing stability of complex constructions which were hit by a launched missile. The algorithm, called Vertical Impact (VI) is based on intuitions similar to those used by Renz and Zhang in the ERA-based approach, however it also considers a potential impact that objects lying on an object $o$ can have on its stability. VI recursively investigates the whole construction lying on and below an object hit by a missile and checks whether a gravity force acting on a block or a block structure outweighs opposite forces acting on it and cause the block (structure) fall.

## References

1. Blum, M., Griffith A., & Neumann B. (1970). A stability test for configurations of blocks. Artificial Intelligence Memo, (188), 1970.
2. Siskind, J. M. (2000). Visual event classification via force dynamics. In Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on on Innovative Applications of Artificial Intelligence, 149–155, Austin, TX, USA.
3. Siskind, J. M. (2004). Method of determining the stability of two dimensional polygonal scenes. United States Patent, (US 6,693,630 B1), 1–19.
4. Wałega, P. A., Zawidzki, M., & Lechowski, T. (2016). Qualitative physics in angry birds. IEEE Transactions on Computational Intelligence and AI in Games, 8(2), 152–165.
5. Zhang, P., & Renz, J. (2013). Qualitative spatial representation and reasoning in Angry Birds: First results. In 27th International Workshop on Qualitative Reasoning, 123.
6. Zhang, P., & Renz, J. (2014). Qualitative spatial representation and reasoning in Angry Birds: The extended rectangle algebra.