The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

MSc Thesis #9818

Title:Planning and Assembling Pentominoes
Date: 1998
Abstract:This thesis faces the problem of planning and assembling a pentomino puzzle. The parts of the puzzle are composed by five squares in different arrangements. They are placed in an 8-by-8 board. The pieces are represented in PROLOG clauses and an algorithm was constructed to traverse the search space created by all the possible states of the board derived by different dispositions of the 12 parts in the board. The space is huge and thus heuristics are needed to prune portions of it. The most successful one discards the states where the empty squares of the board are not grouped in numbers multiple of 5.The solutions of the puzzle are assembled in the real world by a robotic arm. The parts, which are restricted to move on a plane, are inserted in order in the board in such a way that collisions between them are avoided. To achieve that, the parts which lie close to the middle of the board must be insered first. Gaps between the parts are provided to help the safe movement of the parts. Finally the robot is enhanced with two behaviours (gripping and sweeping) to execute the calculated motions of the parts.

[Search These Pages] [DAI Home Page] [Comment]