TY - JOUR

T1 - Partitioning de Bruijn graphs into fixed-length cycles for robot identification and tracking

AU - Grubman, Tony

AU - Sekercioglu, Y. Ahmet

AU - Wood, David R.

PY - 2016/11/20

Y1 - 2016/11/20

N2 - We propose a new camera-based 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 k-cycles 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 k-cycles, then dB(q,tℓ) can be partitioned into tk-cycles for any divisor t of k. The methods used are based on finite field algebra and the combinatorics of words.

AB - We propose a new camera-based 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 k-cycles 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 k-cycles, then dB(q,tℓ) can be partitioned into tk-cycles for any divisor t of k. The methods used are based on finite field algebra and the combinatorics of words.

KW - de Bruijn graph

KW - Graph decomposition

KW - Graph theory

KW - Linear feedback shift register

KW - Pose estimation

KW - Robot network

UR - http://www.scopus.com/inward/record.url?scp=84995527929&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2016.05.013

DO - 10.1016/j.dam.2016.05.013

M3 - Article

AN - SCOPUS:84995527929

VL - 213

SP - 101

EP - 113

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -