RE: Routing and behavioural norms?

Hi Dave,

That looks like an interesting project. I have done some work on Bayesian learning of norms from observation, which could be relevant here:

Stephen Cranefield, Felipe Meneguzzi, Nir Oren, Bastin Tony Roy Savarimuthu,
A Bayesian Approach to Norm Identification.
ECAI 2016,
https://ebooks.iospress.nl/publication/44807

Stephen Cranefield and Ashish Dhiman,
Identifying Norms from Observation Using MCMC Sampling,
IJCAI 2021,
https://www.ijcai.org/proceedings/2021/17

I am wondering, though why you would need a distributed norm learning approach in a warehouse. Perhaps the norm synthesis approach proposed by Maite López-Sánchez and colleagues in various publications might be a better fit (search for "synthesis" at https://scholar.google.com/citations?user=ABr4UU4AAAAJ and also see the tutorial at https://www.maia.ub.es/~maite/teaching/NormativeMASTutorial2015TOTv55.pdf). That approach assumes there is an empowered and benevolent central agent that monitors the multi-agent system for conflicts and then it generates and announces new norms to resolve the conflicts.

Regards,
Stephen

From: Dave Raggett <dsr@w3.org>
Sent: Thursday, June 1, 2023 8:06 PM
To: public-webagents@w3.org
Subject: 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<mailto:dsr@w3.org>>