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

DOI10.1016/J.DAM.2016.05.013zbMATH Open1344.05114OpenAlexW2145472417MaRDI QIDQ313805FDOQ313805

Authors Tony Grubman, Y. Ahmet Şekercioğlu, David R. Wood

Publication date 12 September 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.02199

zbMATH Keywords

graph decompositionpose estimationde Bruijn graphlinear feedback shift registerrobot network

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Artificial intelligence for robotics (68T40)

Abstract: 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, $ell$. 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 $extdB(q,ell)$. We provide several existence results that give the maximum number of cycles in $extdB(q,ell)$ in various cases. For example, we give an optimal solution when $k=q^{ell-1}$. Another construction yields many cycles in larger de Bruijn graphs using cycles from smaller de Bruijn graphs: if $extdB(q,ell)$ can be partitioned into $k$-cycles, then $extdB(q,ell)$ 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.

Recommendations

• Colouring of cycles in the de bruijn graphs
• On the de Bruijn torus problem
• Generalized de Bruijn graphs
• scientific article; zbMATH DE number 1890156
• Binary de Bruijn cycles under different equivalence relations

Cites work

• scientific article; zbMATH DE number 4021187 (Why is no real title available?)
• scientific article; zbMATH DE number 3677839 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 734466 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A Gray Code for Necklaces of Fixed Density
• A Survey of Combinatorial Gray Codes
• A proof of Golomb's conjecture for the de Bruijn graph
• A solution of Dudeney's round table problem for an even number of people
• Asymptotic lower bounds for Ramsey functions
• Cycle decomposition by disjoint transpositions
• Cycle decompositions of complete graphs
• Cycle decompositions. IV: Complete directed graphs and fixed length directed cycles
• Cycle decompositions. V: Complete graphs into cycles of arbitrary lengths
• Normal Recurring Decimals
• Resolvable coverings of 2-paths by cycles
• Rigid graph control architectures for autonomous formations
• The combinatorial power of the companion matrix
• The lexicographically least de Bruijn cycle

This page was built for publication: Partitioning de Bruijn graphs into fixed-length cycles for robot identification and tracking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q313805)