In the future nano-robots could be used in in-vivo medical applications. By using lattice robots as a unit of measurement tumours could be assessed as malignant or benign by considering the shape of their boundaries through cooperative object recognition. With the objective of moving towards this end goal research has been carried out using simulations on hexagonal lattices that allow simple agents to cooperate to distinguish between two objects' shapes. This paper determines a method which gives a value of di erence between any two objects constructed on a hexagonal lattice. This di erence value will provide a metric for future cooperative object recognition scenarios. The measure of the di erence value was calculated considering varying degrees of knowledge about sections of the objects' boundaries. The results were compared to a simulated task with agents that were homogeneous, anonymous, had a limited sensor range and no common coordinate system. It was found that the di erence value metric provides a signi cant correlation to the time taken to complete a series of cooperative object recognition scenarios.
With continuing advances in miniaturising electronics there is an increased amount
of interest in nano-scale robots for medical applications [
Utilising a swarm robotic approach cooperative object recognition is
achievable, where individuals who cannot assess an object alone can cooperate to
identify an object through interacting with it and the other members of the
swarm. In addition to the miniaturisation of robots, this method will potentially
allow for swarms of nano-robots who can identify unwanted or dangerous
entities in human bodies through shape analyses. For example tumours that can be
assessed by their shape to determine if they are malignant or benign [
Groups of homogeneous lattice robots, who individually are approximations
of regular shapes, can connect together into ordered formations. Two-dimensional
lattice structures can be formed and rearranged by triangular, square and
hexagonal robots [
One advantage of lattice based robots, especially where smaller sized and
simpler robots are considered, is their ability to become a unit of measurement.
Giplin and Rus [
To determine a metric a method is required for comparing two objects' shapes
similarities to each other whilst considering how much information is currently
known about them. The object shapes in a hexagonal grid-world could be
considered binary images and the arena the background. Shape coding has been used
to store binary images in a range of di erent ways [
By determining a method of describing the boundary of objects' shapes on a hexagonal lattice, without considering their location and rotation, this paper provides a metric for comparing two object shapes. This metric is then tested using a series of cooperative object recognition scenario simulations involving a swarm individually simplistic agents. 2
In order to understand what the metric will be measuring the simulation platform rst needs describing. This research uses a hexagonal lattice as an arena for testing cooperative object recognition tasks. Each hexagonal cell can be: an object cell, which are grouped to form object shapes; a single agent, termed a hBot; a border, which the hBots cannot pass; or an empty space. 2.1
Object Shapes Object shapes are constructed by grouping a number of neighbouring hexagonal object cells together, where the simplest object shape is a single cell. An object shape can be described without considering rotation or location by the contours of its boundary region, this is termed the data-chain. If each cell that neighbours an object shape is given a value determined by how many object cells it touches, the data-chain is an array of these values arrange in a clockwise manner represented by the sequence which is rst in lexicographical order. All the object shapes with four object cells (ID0 - ID9) are shown, Fig. 1, with the numbers in each of their surrounding cells indicating how many object cells they neighbour, resulting in the data-chains listed.
A scenario is de ned by the two object shapes that the hBots must cooperate to distinguish between. In a scenario one of the object shapes is classed as valid, this is the object shape the hBots must identify and remove. The other object shape is invalid; this object shape must not be removed by the hBots. It is the di erence between these two object shapes which determines the di culty of the scenario which the metric will determine (section 3.0). The hBots used in the cooperative object recognition task are homogeneous, anonymous, have no common coordinate system and are not aware of their position relative to the arenas coordinate system. The hBots are modelled with local sensor and communication, both with a range of one cell. This capability allows the hBots to determine their current state from their immediate surroundings and to communicate this state to any hBots that they neighbour, providing a feedback loop between neighbouring hBots. The current state-level of the hBot indicates how much knowledge it has about the object's shape, whilst the state of the hBot describes this knowledge speci cally.
{ A hBot at state-level 0 is not in contact with an object shape and therefore has no knowledge about the object shape, this is state 0. { A hBot at state-level 1 knows the number of object cells it is neighbouring: one, two, or three and is equivalent to knowing a single value in a datachain. This knowledge is represented by states 1, 2 and 3 respectively. This value could theoretically be between one and six, however in this research the object shapes were limited as to only allow situations where the values one, two and three occur, to initially reduce the total number of states. { A hBot at state-level 2 knows as much as three individual agents at statelevel 1, as it knows its own state-level 1 state and the states of its neighbours. This is equivalent to knowing three consecutive values in a data-chain and includes states 4 { 21. { A hBot at state-level 3 knows as much as ve individual agents at statelevel 1, or three agents at state-level 2. This is equivalent to knowing ve consecutive values in a data-chain and includes states 22 { 264.
As certain states are only achievable when the hBots interact with certain
object shapes, these states can be used by the hBots to distinguish between
object shapes. The total number of states, 265, is determined in part by the
number of object cells the hBots can distinguish between, the way the hBots
move from one state-level to the next and the possible states the hBots can
reach whilst neighbouring each other. A hBot does not distinguish between the
position of its neighbours; when hBots determine their next state they do so by
sending its own state and the states of its neighbours to the state-rule table with
the following format: [own][lowest neighbour][highest neighbour]. This means
that the symmetrical features of the object shape, as described by sub-chains
from the data-chain, will appear identical. For example: where two sets of three
hBots are neighbouring similar parts of object shapes that are mirror images
of each other, Fig. 2. The hBot A neighbours an object shape with the
datachain f1,1,1,2,2,1,2,1,1,1,3,2g and the hBot B neighbours an object shape with
the data-chain f1,1,1,2,1,2,2,1,1,1,2,3g. The three hBots including hBot A are
on the sub-chain ff1,3,2gg and the three hBots including hBot B are on the
sub-chain ff2,3,1gg. Although these sub-chains are di erent the resulting state
of hBot A and hBot B at state-level 2 will both be the result of referencing the
state-rule table with values [
For each time-step hBots move with equal probability to any of their neighbouring cells, unless the cell is an object cell or a border cell. If an hBot attempts to move into a cell containing another hBot it instead remains stationary. When next to an object cell the hBot generally stays still. However, the hBot has a probability, determined by its state, of moving away from that cell: 0.01 if it is a common state to both object shapes or it is only achievable for the valid object shape and 0.1 if it is only achievable for the invalid object shape. This increases interaction around the object shapes whilst reducing the chance of stagnation. If the hBots simply remained stationary, they could be divided amongst multiple object shapes or parts of object shapes without enough neighboring agents interacting to distinguish between those object shapes.
Given a data-chain of an existing object shape it is possible to determine which states at which state-levels are achievable for a group of hBots by examining sub-chains, represented by a double curly bracket, of lengths one, three and ve. De nition 1. At sub-chain length one the single number in the sub-chain is equal to that of the state of the hBot in contact with the object shape at that same location.
{ ffAgg becomes state [A].
At sub-chain length three a conversion is required complicated. The sub-chain must rst be re-ordered and then the relative state of the hBot must be found. { ffA,B,Cgg becomes [B][lowest of A and C][highest of A and C] which returns the new current state for the hBot at position B.
At sub-chain length ve two stages of conversion are required. First three, three length sub-chains must be found and then the relationship between these three needs to be found to give the nal state.
{ ffA,B,C,D,Egg is broken into three ffA,B,Cgg , ffB,C,Dgg and ffC,D,Egg. { ffA,B,Cgg becomes [B][lowest of A or C][highest of A or C] giving state P. { ffB,C,Dgg becomes [C][lowest of B or D][highest of B or D] giving state Q. { ffC,D,Egg becomes [D][lowest of C or E][highest of C or E] giving state R. Now there is a sub-chain ffA,P,Q,R,Egg and Q can be resolved. { ffP,Q,Rgg becomes [Q][lowest of P or R][highest of P or R] which gives the nal state for the hBot at position C.
This method is used as it considers the way in which the hBots interact with both each other and the object shapes' boundaries. Sub-chains of lengths, one, three and ve, relate to the information that one, three and ve hBots could gather. Considering each sub-chain in the data-chain, is equivalent to considering each position that a group of hBots could interact with the boundary of the object shape.
For example the data-chain of object shape ID0, f1,1,2,1,2,1,1,2,1,2g, is examined to nd the hBots' achievable states at state-level 1, 2 and 3 when interacting with the object shape, Table 1. These achievable states are compared to those of object shape ID1, f1,1,1,2,2,1,1,2,1,1,3g, in Table 2 where the di erence value is found by dividing the number of achievable states at each state-level that are not present in the other object shape by the length of the data-chain. The achievable states which are not possible in the alternate object shape are highlighted bold. This represents the number of positions that a hBot could determine that it is next to one object shape and not the other and the number of cooperating hBots required to do so. The di erence value for each combination of object shape pair was determined, excluding object shape ID6. This object shape was not included as it was the only object shape to include a 4 in its data-chain. The results are shown for achievable states at state-level 1, 2 and 3 in Fig. 3, left, centre and right, respectively. From these heat maps it is shown that the higher the state-level the more di erent the object shapes appear. It also shows that object shape A's di erence value from object shape B is not the same as B's from A. This lack of symmetry is due to the indiviual features of the boundary of the object shape that sub-chains describe. If a feature is common to two object shapes that are compared then it cannot be used to distinguish them. If a feature is unique to one object shape that feature can be used to distinguish it from the other but not vice-versa. Therefore, it is possible to have two object shapes where one is easier to distinguish from the other due to the unique features it has. Finally the heat maps show that object shape pairs: ID1 and ID2, ID5 and ID7, ID4 and ID8 are indistinguishable, this is due to them being mirror images of each other.
The arena in which the tests were performed was hexagonal with each of the six sides measuring 21 cells. Within the arena six of each of two types of object shapes were placed as shown in Fig. 4. One of these object shapes was classed valid for removal and the other object shape was classed as invalid. Thirty-seven hBots were placed at the centre of the arena in a tight cluster at time-step zero. Whenever a hBot reached a state that was achievable for only the valid object shape, the object shape it was neighbouring would be removed instantly, as if dissolved. The number of time-steps it took the swarm to remove all of the six valid object shapes was recorded.
All possible pairs of object shapes with four object cells were tested excluding object shapes that mirrored each other and object shape ID6. These object shapes were not included because mirrored object shapes are perceived as identical in this system and object shape ID6 is the only object shape with a number 4 in its data-chain. Currently the system is only capable of distinguishing object shapes with numbers 1, 2 and 3 in their data-chains. Each experiment was run fty times with both object shapes classed as valid and invalid in turn. Algorithm 1 describes the simulation, hBot and object shape interaction used. The average number of time-steps it took to complete each of the 30 cooperative object recognition tasks was compared to the mean of the three di erence values found for the same two objects, as shown in Fig. 5. These results have a correlation coe cient of -0.78.
By considering only the di erence values at each state-level individually an indication of how the number of cooperating hBots a ect their ability to distinguish the object shapes. At state-level 1 there was a correlation coe cient of -0.48. However, this is less than the di erence values at state-level 2 and state-level 3 which have correlation coe cients of -0.73 and -0.84 respectively. This suggests that the hBots that reach only state-level 1 have a lower e ect on whether or not the object shapes will be distinguished from one another. 5
A method was proposed for determining the di erence value between two object shapes. This was done by comparing sub-chains at lengths one, three and ve of the data-chain that represents the object shape. Unlike chain-coding a data-chain Algorithm 1 The Simulation, hBot and object interaction repeat for each hBot i do if hBot[i] state == a unique valid shape state then object neighboring hBot[i] is deleted hBot[i] state = 0 else if hBot[i] state == a unique invalid state then
10% chance of hBot[i] state = 0 else then
1% chance of hBot[i] state = 0 end for Update contents of all cells for each hBot i do hBot[i] senses surroundings if hBot[i] state == 0 then
hBot[i] moves to random neighboring cell if empty does not have information on its location or orientation which makes it possible to compare the shapes to each other without considering these two factors. To measure the accuracy of the found di erence values a series of experiments were run with a range of four cell object shapes. These experiments determined how long it would take a swarm of hBots to remove six valid object shapes whilst ignoring six invalid object shapes.
The results showed a signi cant correlation between the di erence values representative of each of the state-levels with the amount of time-steps it took the hBots to complete the cooperative object recognition task. As expected, where only the states achievable by hBots at state-level 1 are considered in the di erence value measurement there was a lower strength correlation. This is likely due to the hBots being generally unable to distinguish between the object shapes on their own, with the exception of object shapes ID0 and ID9 which are the only object shapes without a 3 in their data-chains. Therefore, any other object shapes can be distinguished from them by a state-level 1 hBot in state 3.
This shows that the di erence values give a clear indication of how di cult it is for a swarm of hBots to complete a cooperative object recognition task based on the di erence between the boundaries of the object shapes. Using this information it will be possible to derive future task scenarios with a suitable range of di culties for comparing di erent scenarios and techniques for cooperative object recognition. An area of interest is training the hBots to determine the correct behaviours to distinguish between the object shapes with limited feedback.
Due to the methods chosen for completing this investigation there were some limitations to the simulation platform and limitations in the way in which the agents were modelled, which should be addressed in future research: { The use of a synchronized grid-world reduced the similarity with physical systems. { Using a less common hexagonal lattice, comparisons with existing multiagent systems are di cult to make. { All the agents were modelled with perfect sensors and communication, it would be interesting to see the e ect of miscommunication on the systems capability to identify objects correctly. { The system only deals with object shapes that have the values 1, 2 and 3 in their data-chain, ignoring possible shapes that have the values 4, 5 and 6, to reduce the state relationships possible. { The hBots cannot distinguish between hollow shapes and solid shapes, as they only currently interact with the outer boundary of the object shape and have no means of communicating to other hBots inside the hollow if they were there. { Object shapes that are mirror images of each other appear identical due to the way the hBots sense their surroundings. { Currently the number of state-levels would only allow a single hBot to have the equivalent knowledge of ve state-level 1 hBots. This means that certain shapes currently would not be possible to distinguish from each other.
Overall the di erence value metric will be a valuable tool for future studies in co-operative object recognition research with hexagonal grid-world simulations.