BARD: The Bonaventure Automated Robotic Delivery System
Shelley McClarigan
Robert Harlan
Copyright 2000

Abstract
The Bonaventure Automated Delivery System (BARD) was designed to test the efficacy of the kRobot© class as an interface for the Khepera robot. The system features a centralized planning system that, given a set of mail messages addressed to various offices, determines a plan for carrying out the deliveries in the most efficient manner and then carries out the plan.
    Shelley McClarigan completed the BARD project in 1999-2000 academic year at St. Bonaventure University in partial fulfillment of the requirements for an honors degree. Robert Harlan, the project advisor, edited this document. A copy of the original honors project can be found here.

Introduction
The traditional approach to robotics features a centralized planning agent that is responsible for constructing and carrying out plans. The construction of a plan requires that an agent examine different alternatives and select the best one. To carry out the plan, the agent must use its sensors to perceive the world and its effectors to move about in the world. 

Figure 1: BARD's World

    The Bonaventure Automated Delivery System (BARD) is an example of the traditional approach to robotics. An autonomous robot, capable of perceiving and moving about in its environment, is given a set of messages to deliver to different offices. It must construct a plan to deliver the messages in the most efficient manner and then carry out the plan. 
    The robot used for the project is the Khepera miniature robot, which is the platform chosen for St. Bonaventure’s robotics lab. The robot operates in a tethered mode: the control program is run on a host computer, in this case a Sun Ultra workstation, and communication with the robot takes place through the serial port of the computer. The host computer can monitor the robot’s sensors and effectors and can control the effectors. 

Picture 1: BARD in action

    One goal of the project is to determine the efficacy of the kRobot© class, the interface we designed for the Khepera robot. It encapsulates and hides low-level serial communication between the host computer and the robot, enabling the programmer to focus on behavior control algorithms. In this case, we built behaviors relevant for delivering mail in an office such as following walls, turning and recognizing offices. 

BARD’s World
BARD’s world is a physical model of an office complex, a rectangular office suite with offices numbered incrementally from 101 (Figure 1 and Picture 1). There is one exterior corridor, and the exterior walls of the complex measure 3’ by 2.5’. The base is made of ¼” pegboard, and walls are constructed of 2” high poster board. The complex is set on a table next to a Sun workstation.

Basic Behaviors
In order to carry out the task of delivering mail, the robot must be able to find its way around the office complex. This involves following walls, turning corners and recognizing offices. 

Figure 2: Finding a wall

    The first behavior developed was wall following: the robot would follow walls until it reached a corner or an office. 
    The ability to follow a wall, however, required first that the robot find a wall to follow. The robot's proximity sensors were used to determine if it could see a wall. If it could then it could begin wall following, otherwise, the robot needed to move a little closer to the wall, and check the sensors again. The MoveFoward() and TurnRight() functions were used alternatively accomplish this.
    The FindWall() algorithm, illustrated in Figure 2, is:

 while a wall is not in view
    TurnRight()
    MoveForward()

    Wall following was more difficult to implement than expected. Since the robot’s motors are not perfect, the robot never quite moves in a straight line. Eventually the robot either runs into the wall or drifts far enough from the wall. 
    The problem of running into the wall is easy to fix with the robot’s proximity sensors: we prevented the robot from running into walls by setting a limit on how close the robot could be the wall. If the robot’s sensors returned a value that was higher than the limit (high numbers mean an object is very close), it turned away from the wall slightly. 

Figure 3: Drifting away from the wall

    The problem of drifting away from the wall was more difficult. If the robot no longer sees the wall it is following, it is in the same perceptual state as it is when it encounters an office door or a corner. 
    After repeatedly monitoring sensor data to determine what the robot ``sees’’ as it drifts or as it reaches an office or a corner, we noticed that the proximity sensors dropped much more quickly in value when the robot was at an office door or corner than when it was drifting. The solution was to compare the proximity reading of the side sensor with the previous reading of the same sensor. If the difference between them was greater than a threshold value, the robot had reached a corner or a door, otherwise it was drifting (Figure 3).
    The remaining behaviors relevant to the delivery system, viz., turning corners and entering and exiting offices, posed no great problem. To enable the robot to navigate the offices both clockwise and counter-clockwise, it was necessary to find walls, follow walls, enter offices and turn corners either on the left or right. This was relatively simple as the sensors are symmetric: the robot read from the sensor(s) on its other side to follow walls, etc., and turned in the opposite direction at corners and offices.

Creating the Planning System
The goal of the planning system was to determine the most efficient way to deliver messages to offices. This requires that the robot be able to represent the spatial relationships between offices in the complex and then determine which route would be the shortest to deliver the messages.
    The representation of a space such as an office complex can be either grid-based or topological. In the former case, each significant point in the space is given an absolute address. Given its current position and the ability to monitor its change of position by noting wheel rotations, the robot could navigate a course from its current position to the goal position. A topological representation, on the other hand, assigns each object a location relative to other objects. If the robot is at office 102, it knows the next office is 103.

Figure 4: BARD's internal representation of the office complex

    Reflection on how we humans navigate a well-known space such as an office complex suggests that the representation should be topological. Offices are assigned numbers that indicate relationships to other offices. What we know about the offices is there relationship to one another rather than their absolute positions in space. 
    The topological representation developed is shown in Figure 4. The offices are numbered in ascending order: moving in a clockwise direction from office 101, the robot can visit the offices in order. Note that the corners are labeled as well. Corner A is the corner between offices 101 and 102.
    The object “Me” in the center is BARD. Each node in the list contains a name and a type. In this case, BARD is pointing to Office 103, signifying his current location in the world. It can follow the arrows to see that if he moves in a clockwise direction around the suite, the next thing it will encounter is Corner C, and after that Office 104. It can also derive that he has just passed Corner B, and before that Office 102. This representation of space can be used, given the assumption that the distance between any two offices is the same, can be used to determine the most efficient path to deliver messages.
    To determine the shortest path between two offices, proceed in the direction in which there are fewer offices between the robot’s current location and the office it must go to. For example, if the robot is at office 103, it can see that it will pass two offices on its way to office 102 if it moves clockwise, but it won’t pass any if it moves counterclockwise. Proceeding counterclockwise is obviously more efficient, and is the route it would choose. 
    BARD carries out the plan by using its wall finding, wall following, and corner turning behaviors. As each office is passed, the robot’s position is updated. It checks to see if the office matches its destination: if it does, it enters the office, if not, it continues to the next office. Adding the capability to handle multiple messages for multiple offices completed the planning system. Messages for offices that were closest to the robot’s current position were given higher priority, so the first thing BARD has to do is figure out how far (moving both clockwise and counter-clockwise) each message’s destination is from its current location. The following algorithm determined the order of delivery:

while there are messages to deliver

If there is one message, then go directly to the office that message is bound for.

If there is one destination that is closer than any other, then deliver message(s) at the closer destination. 

If there are messages for two destinations of equal distances from the current position, but one destination has more messages for it than the other, then go to the office with the most messages waiting to be delivered. 

If there is the same number of messages for both the two closest offices, then got to the next office in the direction the robot is currently moving.

After each destination is reached and the messages have been delivered, BARD asks if there are any more messages that need to be delivered. It then recalculates, if necessary, the priorities of the messages now in its possession, and continues to the next office.

A complete description of BARD’s planning mechanism is available here.

To download BARD click here (** NOTE**  BARD uses kRobot version 1.0)

Back to Robotics Page

Back to the Computer Science Home Page

Last update: 8/2000