A Technique For Planning In A Blocks World Environment

A Technique for Planning in a Blocks World EnvironmentVincent Tat Robert McLarenDepartment of Electrical and Computer Engineering,University of Missouri,Columbia, Missouri 65211AbstractA method for moving blocks, referred to as "blocks world ", is described in a bookon LISP by Winston and Horn. In simplifying that implementation, the basic methodavoids using a physical coordinate system for the blocks and the gripper. This"trade -off" leads to the question as to how a block is moved from one location toanother. This paper presents a method to augment the basic scheme by proposing athree -dimensional coordinate system. The proposed method can generate a path formoving a block from one location to another without encountering any obstacles. Thispath is described by the three -dimensional coordinates. With an appropriate graphicsprogram, one can project the coordinates to effect a dynamic graphics display of ablock along the path. In the context of a "real world" robotics system, the gripperis moving a block autonomously after being given the initial state of the environment,represented possibly by the output of an image process and a description of the objectto be moved. Appropriate computer programs are included to illustrate how the methodis implemented.IntroductionA blocks world scheme, implemented in LISP, is described in Ref. (1). Thegeneral task or objective of the scheme is to create a plan to allow for theimplementation of blocks world commands. The command involve picking -up one object orputting one object on another. In the process of moving objects, obstructions aremoved out of the way at the starting (departure) point and at the final (destination)point. There are no constraints imposed on the path between these two points.Therefore, it is not clear what the path of traversal is. In an extreme case, theexistence of such a path may be questionable as for example, in the case where thereare obstacles along the path. This paper introduces the use of physical coordinatesin the scheme. Also, a path is planned between the departure and destination points.As a result of planning, the path for the block and gripper will be free of obstacles.For each incremental move, the coordinates of the moving block form part of the outputso as to allow for a three -dimensional projection of the principle objects to bedisplayed on the monitor for visual inspection.ApproachIn order to reduce computation time, a Cartesian coordinate system is defined,using the y -axis as height, the x -axis as width, and the z -axis as the depth. Thereference plane or "table" is coincident with the XZ coordinate plane. Each block orcube is one unit by one unit by one unit. The area of activity on or above theXZ -plane is 3 units by 3 units. There is a total of 6 cubes or blocks in this basicstudy, with 3 of them being left stationary as obstacles. A further limitation inthis study to demonstrate the planning technique is to restrict the action to a 3 unitby 3 unit by 2 unit volume. The total action volume is partitioned into two levels,each of which can be visualized as a 3 by 3 grid, labelled from 0 to 8 as aone -dimensional array, as illustrated in Fig. 1. The use of numerical values enhancesprocessing speed. If, at any time, a real or "actual" coordinate value is needed,then a coordinate conversion look -up table or routine can be applied to derive it.When a space cell is occupied by a block, the "name" of the block is stored asthe value of the corresponding array element. Otherwise NIL is stored at thatlocation. With this arrangement, a scanning of a space cell array reveals where andwhat occupies a cell.A block, identified by a unique name, has three properties: position, "supportedby ", and directly supports. In blocks world, the blocks are moved around by a robothand or manipulator which has grasping and positioning capabilities. Because thefocus of this paper is the blocks and their positions, no attempt has been made todetermine a path for the hand when moving the hand alone. However, the hand itself