Heuristic Reasoning for 2D Containment Problems

 

Nuno Marques, João Bernardo and Pedro Capela

Instituto Nacional de Engenharia de Sistemas e Computadores,

Avenida Duque d’Ávila 23, 1000 Lisboa, Portugal

{nrm,jcb,pmc}@trabi.inesc.pt

 

 

ABSTRACT

Industry nowadays seeks for automation in processes that, until a few years ago, were mainly dependent on human work and intelligence. Containment problems belong to that family of automation processes. We can define a containment problem as a way of placing a set of shapes into another shape without overlapping. In this paper we apply A. I. concepts such as A* informed search algorithms to solve 2D translational containment problems. A containment problem can be described through a search problem and solved by using a heuristic that makes A* search complete and optimal. Morphological operators define the geometric description of the state space. To implement morphological operations, discrete mathematics is applied, allowing us to change the complexity analysis from the polygonal vertex/edge approach to the discrete unit/area approach.

Keywords: Containment Problems, Geometric Algorithms, Heuristic Search, Morphological Operators, Admissible Heuristics.