Autonomous delivery robot

The town: streets, houses, the supermarket in the middle and the robot at its loading pad, with order pins over two houses.

The task

The robot lives at the supermarket in the middle of town. When people order something, it loads up their parcels, drives them round to each house and heads back. It can only carry three at a time, so on a busy day it's back and forth a lot.

What makes it interesting is that nothing stays put. New orders come in while it's out on the road, and streets get blocked without warning, sometimes the exact one it was about to turn into. If it just followed a route worked out at the start, it would be stuck within minutes. Instead it keeps checking what's changed and adjusts as it goes. That's what the MAPE-K loop is for.

The MAPE-K loop

MAPE-K is a reference model for self-adaptive systems, introduced by IBM for autonomic computing. A controller observes the system it manages, decides whether anything needs to change, plans a response and carries it out, with all four steps sharing one knowledge base. The robot runs this loop a couple of times every second.

Monitor

Reads the robot's position and cargo and the current roadblocks.

Analyze

Decides whether an adaptation is needed: a trip is due, the route is blocked, a roadblock was cleared, or the robot has reached a customer or its base.

Plan

Computes the route and the order of stops. If no route exists, the plan is to wait.

Execute

Moves the robot, loads and hands over parcels, and switches to new routes.

Knowledge

Shared by all four steps: waiting and loaded orders, the current route, the state of the trip, and metrics such as distance, re-plans and delivery times.

One pass of the loop. Plan only runs when Analyze finds that something has to change; otherwise the robot keeps following its current route.

Adaptation in practice

Placing orders

A house with an order pin and a card showing its waiting and delivered orders. — Clicking a house adds an order to the queue. A trip starts when three orders are waiting, or 30 seconds after the first one, whichever comes first.

The departure countdown, part-way drained. — Clicking a house adds an order to the queue. A trip starts when three orders are waiting, or 30 seconds after the first one, whichever comes first.

Planning the trip

Top view of the town during a trip: a blue route through the delivery stops and a red route back to the supermarket. — Blue legs lead to customers; the red leg returns to base. The stops are visited in the order that makes the whole trip shortest.

A roadblock on the route

A roadblock on a street, with the robot's route bending around it. — When a roadblock lands on the route, the next pass of the loop detects it and re-plans the remaining stops from the robot's current position.

No route available

The robot boxed in by roadblocks, with a red exclamation mark above it. — If every way out is blocked, there is no valid plan, so the robot waits in place with its parcels. When a roadblock is removed, it re-plans and continues.

Route planning

Paths between two points are found with A* search, using the Manhattan distance as the heuristic. On a grid where the robot moves in four directions this never overestimates the remaining distance, so A* always returns a shortest path.

The order of stops is a small travelling-salesman problem. With three parcels there are only six possible orders, so the robot evaluates all of them and keeps the shortest. Ties go to the order that reaches customers sooner.

After a roadblock, the robot re-solves the whole sequence rather than just the next path, because a change in the streets can make a different order of stops the better one.

Limitations

Perfect sensing. The robot knows about every roadblock as soon as it appears. A real robot would only detect obstacles nearby.
No learning. The knowledge base stores the current state, not past experience, so the robot cannot anticipate streets that are often blocked.
Simple dispatching. Orders are served first come, first served by a single robot. Grouping nearby orders or coordinating a fleet would reduce delivery times.

Place a few orders, add some roadblocks, and watch it adapt.

Play the simulation