Routing and behavioural norms?

I’ve been working on a web-based simulation of a swarm of robot forklifts in a warehouse:

 https://www.w3.org/Data/demos/chunks/warehouse/

This work in progress, and the next step is to integrate automate route planning.  My initial approach has been to use the A-star algorithm across a grid of cells and to combine it with pheromone traces to enable collective learning.

The following web page randomises the origin and animates the search process. Use the retry button to select a new origin and initiate search for the destination:

 https://www.w3.org/Data/demos/chunks/warehouse/search/

This shows that the A-star algorithm can provide far from optimal routes compared to what a human would devise. Some explanations for this include:

Search is essentially blind and feels its way around obstacles
Limited beam width may result in promising routes being forgotten
Routes may have kinks despite heuristics to avoid them
Search finds the first solution, but further solutions may be better

A more promising approach is to treat the obstacles as defining a set of interconnected spaces with open areas, junctions and alley ways. In other words to convert the map of obstacles into a connectivity graph. The different spaces can then be associated with different heuristics, along with statistical priors and learnt behaviours. Pheromone traces provide one means to support a collective memory. I am working on a new demo to showcase how this can work.

A more ambitious goal will be to consider how to enable swarm agents to learn behavioural norms from their interaction with other agents, including ideas learned indirectly from other agents, courtesy of the hive mind.

Human drivers, for instance, learn when to give way to oncoming vehicles in narrow streets with parked cars as obstacles, and how to signal to each other via changes in speed and position, along with the turn indicator lights. At least in the UK, we also use our hands to thank the driver who gave way, and likewise, to acknowledge that gesture.  At night we flash the car’s headlights to say thanks.

Anyone interested in collaborating on this?  The warehouse is just one of many scenarios. Others include simulating urban traffic in cities, simulating smart factories, and logistics for container sea ports.

p.s. the underlying framework involves a collection of mobile and static agents that communicate using asynchronous messages. Cognitive control is based upon rules operating on knowledge graphs, inspired by John Anderson’s ACT-R architecture.

Best regards,

Dave Raggett <dsr@w3.org>