This work is supported by the European Union's Horizon research and innovation programme under grant agreement No. 101092908 for project SmartEdge on swarm-based orchestration for the IoT.
This is a laboratory for developing routing algorithms for the forklifts in an automated warehouse. The idea is to combine the A-star search algorithm with traces of pheromone vectors deposited by forklifts as they move across the warehouse floor.
The starting point is to divide the floor into a grid of cells and to mark the obstacles to the forklift, i.e. the storage racks for pallets. We then need to search for a reasonable path from the starting point to the destination.
The search proceeds into phases. The first phase starts from the origin and moves towards the destination, exploring the immediately neighbouring cells and prioritising them using the sum of the distance of each cell from the origin and destination. An AVL tree is used for the priority queue and has a maximum size corresponding to the beam width. Geometric distance seems to work better for this purpose than the Manhattan distance. Each cell is then annotated with the minimum number of cells to reach the origin.
The second phase starts from the destination and moves back towards the origin selecting from the neighbouring cells for the shortest path. To reduce kinks, the neighbour with the shortest geometric distance to the origin is used as a tie breaker. A small amount of noise is injected to the keys when inserting cells into the AVL tree to ensure that all cells are queued even when their keys would otherwise be the same.
It is clear that the A-star algorithm can provide far from optimal routes compared to what a human would devise. Some explanations for this include:
Another approach is to use a swarm of ants in a monte carlo search where the ants start from the origin and make random moves, marking the floor with the distance from the origin. The moves are biased to encourage the swarm towards the destination.
A much 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.
The initial goal is to develop code to create the planned move actions for forklifts as they carry out their tasks in the warehouse.
The next step will be to integrate support for biasing routes according to the directions that previous forklifts have taken over any given cell. The traces decay with time, akin to the forgetting curve for human memory.
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.
This work is supported by the European Union's Horizon research and innovation programme under grant agreement No. 101092908 for project SmartEdge on swarm-based orchestration for the IoT.