Projects per year
Abstract
We propose a new camerabased method of robot identification, tracking and orientation estimation. The system utilises coloured lights mounted in a circle around each robot to create unique colour sequences that are observed by a camera. The number of robots that can be uniquely identified is limited by the number of colours available, q, the number of lights on each robot, k, and the number of consecutive lights the camera can see, ℓ. For a given set of parameters, we would like to maximise the number of robots that we can use. We model this as a combinatorial problem and show that it is equivalent to finding the maximum number of disjoint kcycles in the de Bruijn graph dB(q,ℓ). We provide several existence results that give the maximum number of cycles in dB(q,ℓ) in various cases. For example, we give an optimal solution when k=q^{ℓ−1}. Another construction yields many cycles in larger de Bruijn graphs using cycles from smaller de Bruijn graphs: if dB(q,ℓ) can be partitioned into kcycles, then dB(q,tℓ) can be partitioned into tkcycles for any divisor t of k. The methods used are based on finite field algebra and the combinatorics of words.
Original language  English 

Pages (fromto)  101113 
Number of pages  13 
Journal  Discrete Applied Mathematics 
Volume  213 
DOIs  
Publication status  Published  20 Nov 2016 
Keywords
 de Bruijn graph
 Graph decomposition
 Graph theory
 Linear feedback shift register
 Pose estimation
 Robot network
Projects
 2 Finished

Graph colouring via entropy compression
Australian Research Council (ARC)
2/01/14 → 31/12/17
Project: Research

The Structure and Geometry of Graphs
Australian Research Council (ARC)
1/01/08 → 31/12/13
Project: Research