Robot simulation studies

The history of the robot as a concept and as a fact is indicated, and the current linguistic approach to robotology discussed. The problem of designing a robot-controller is approached by taking a simplified, computer-simulated, model of a robot in an environment, and writing programs to enable the robot to move around its environment in a reasonably intelligent manner. The problems of concept representation and the creation and execution of plans are dealt with in this simple system, and the problem of exploration is encountered but not satisfactorily dealt with. The robots' environment consists of a rectangular grid in which squares are labelled as belonging to the boundary, to fixed or movable objects, or to holes, while the robot itself occupies a single square, can sense the labels of the eight surrounding squares, can turn, and can pickup, move, and drop movable objects. The boundary of a typical environment is thus a rectanguloid polygon, which can be compared to the floor-plan of a one-level house. After an initial exploration the basic representation of the environment is as a sequence of edge-lengths and turns, called the ring-representation. An algorithm is described which produces the set of maximal subrectangles of the environment (i.e. rooms, passages, doorways) from the ring representation. To make plans for moving within the environment, the robot first views the maximal subrectangles as the vertices of a graph, wherein two vertices are connected by an edge if and only if the corresponding maximal subrectangles overlap, and then uses a path-finding algorithm to find a path between two vertices of the graph. This path constitutes a "plan of action". Whenever an isolated object or hole is found, its ring-representation is generated and its set of maximal subrectangles produced. Thus the shapes of objects and holes within the environment can be compared in various ways. In particular, an algorithm is described which compares the shape of a movable object with that of a hole to ascertain if the movable object could be moved to fit inside the hole without "physically" moving the object. ROSS, an interactive computer program which simulates the robot-environment model, is described. A command language allows the user to specify tasks for the robot at various conceptual levels. Several problems are listed concerning the ways in which a robot might explore, represent, and make plans about, its environment, most of which are amenable to direct attack in this simplified model. Finally, theoretical questions concerning two-dimensional rectanguloid shapes are raised.Science, Faculty ofComputer Science, Department ofGraduat