This example is a package delivery system. It is a bit more
complex than the elevator system which you can see
here.
The system is a virtual office environment, which models the
graduate labs area in the Department of Computer Science at
York University. This environment is populated by a varying
number of robots capable of delivering packages. The assignment
of packages to robots is the responsibility of a dispatcher.
The dispatcher and the robots implement a variation of contract
net protocol that is used to select the best agent to deliver
a package. The robots can come online and go offline (presumably
after completing the orders they were assigned) at any time.
If no robot can deliver a package the order is queued until
there is a robot available. The GUI is used to get user's
orders and visualize the system by displaying the status and
locations of all the robots in the system.
Implementation
Details
This example is implemented as a multi-agent system based
on OAA architecture. It includes six types of agents of which
five are written in Java and one is written in IndiGolog.
The GUI is mapped into a Swing-based Java agent while the
dispatcher is a simple console-based Java agent.
The robots are actually two-agent architectures that separate
a high-level reasoning subsystem from a low-level motion/orientation/action
subsystem. The IndiGolog-based High Level Control agent (HLC)
is responsible for the implementation of the contract net
protocol and construction of optimal plans for carrying out
the orders awarded to the robot. It takes full advantage of
the IndiGolog-OAA interface through which it can execute its
package delivery plan while responding to requests for bids
coming from the dispatcher and modifying the plan to incorporate
the newly awarded orders. The Java-based Low Level Control
agent (LLC) is simulating the movement of the robot through
the environment. Each robot has a unique ID. This ID is given
to both LLC and HLC and is used by them to find each other
and form a single logical agent while still remaining being two
separate processes. The LLC and HLC can be launched in any order.
The other agents in the system are the PathPlanner and the
DB. PathPlanner agent knows the distances and the routes between
any two locations. The DB agent is the blackboard that is
used by the agents in the system to share information with
each other. The DB stores the bids coming from the agents
and the current status of all the orders. It is also used
to store the queue of unassigned orders.
Select agent to view its implementation details:
Go here to see some typical communication
patterns in the system.
Details: GUI
The GUI is a Swing-based Java agent. This agent graphically
displays the virtual environment with the current location
and status of every robot and package delivery order. It is
also used by the user to give orders to the system. This agent
is multithreaded and all the synchronous calls to the OAA
are executed in their own threads. This way the GUI can accomodate
a large number of robots and orders.
The left-most part of the window is used to display the two
lists of orders: the in-progress list and completed list.
In-progress list shows the status of all the orders that have
not been completed (they can be in progress or queued.) The
completed list shows the orders that have been successfully
completed. The lists show the order number and status. Click
on any order in either list and the tooltip of the list will
show the complete details about the order. The two lists are
not updated automatically by default. You can use the menu
item File|Refresh Order Status or the corresponding toolbar
button to refresh the lists. Alternatively you can turn the
auto refresh on (use File|Turn Auto Refresh ON or the toolbar
button.) This will refresh the status of the orders every 5 seconds.
The middle section of the window is dedicated for the display
of the current robot info. <MORE ON THAT>.
The right-most section of the window shows the map of the
virtual environment. It will be used to pinpoint the location
of each robot. You can drag the locations on the screen.
In order to request a package to be delivered use the menu
item File|New Order or the corresponding toolbar button. Choose
the origin and destination of the order from the drop-down
lists and press 'Order'. The GUI agent will contact the dispatcher
and attempt to place an order. Watch the status bar for the
information on the newly processed order.
The GUI agent has three declared solvables.
All of them are used by the robot agents to update their status.
- action_update(RobotID,Status,Action,Description) - inform
the user which action the robot is currently executing.
Action is a code string for the action. Depending on it
the GUI will show different action icon for the robot. Description
is the detailed description of the action. It will update
the action tooltip. Status is the status code of the robot
- either 'executing' or 'idle'. This determines the status
icon to be displayed.
- position_update(RobotID,CurrentLocation,NextLocation,PerCent)
- update the position of the robot. If the robot is currently
at some location, then NextLocation is an empty string.
PerCent is not currently used. It tells the GUI what percentage
of the distance between the two location the robot has travelled.
- action_position_update(RobotID,Status,Action,Description,CurrentLoc,NextLoc,PerCent)
- this combines the first two solvables. It is used to simultaneously
update the action and the position of the robot.
Details: Dispatcher
Dispatcher's job is to get orders from the GUI agents and
distribute them among available robots. Dispatcher will
assign order number to all the incoming orders and check
the orders for validity. To do the check Dispatcher contacts
PathPlanner agent and finds out the distance between the
origin and destinations of the package. If PathPlanner reports
error, then at least one of the destinations is not in service.
Upon successful check Dispatcher sends request for bids
to all the robots in the sustem. This is part of contract
net protocol that Dispatcher and the robots implement to
select the best robot to deliver the package. OAA functionality
is used here to automatically broadcast the request for
bids to all the agents that have declared such solvable
(capability).
Once requests for bids are sent Dispatcher waits for sertain
number of seconds to allow the interested robots to respond.
Then it gets the bids from DB agent that stores the incoming
bids. After determining the winning robot, Dispatcher notifies
it.
If, however, no robots were able to respond to request for
bids, Dispatcher queues the order by sending queue_order
message to DB agent. Once agents join the system or become
available, DB agent will send requests for bids for all
queued orders to the available robot. When it receives bids
for the orders that are queued, DB forwards them to Dispatcher
through process_queued_order message. The queued order is
then awarded to the bidder and removed from the queue.
Here are the Dispatcher's solvables:
- request_delivery(From,To,Status,OrderNo) - this solvable
is used by the GUI agent to request delivery of a package.
From and To are the origin and destination of the package.
Status is returned by Dispatcher. It is the initial
status of the order. OrderNo is the order number assigned
by the dispatcher.
- process_queued_order(Address,From,To,OrderNo,Distance)
- this message is used by DB agent to notify Dispatcher
of incoming bid for the order that has been queued.
Address is the OAA address of the bidder, From and To
are the origin and destinations of the package, OrderNo
is the order number assigned to the package, Distance
is the robot's bid.
Details: PathPlanner
Details: DB
Details: High Level Control
Details: Low Level Control
Interactions
Here is a sequence diagram picturing the most complete interaction
pattern in the system. Click on the diagram elements to get an
explanation.
|