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

DOI10.1016/J.DAM.2016.05.013zbMATH Open1344.05114arXiv1502.02199OpenAlexW2145472417MaRDI 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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Cycle decompositions. V: Complete graphs into cycles of arbitrary lengths
• Title not available (Why is that?)
• Normal Recurring Decimals
• Rigid graph control architectures for autonomous formations
• Cycle decomposition by disjoint transpositions
• Title not available (Why is that?)
• Asymptotic lower bounds for Ramsey functions
• A Survey of Combinatorial Gray Codes
• A solution of Dudeney's round table problem for an even number of people
• Cycle decompositions. IV: Complete directed graphs and fixed length directed cycles
• Resolvable coverings of 2-paths by cycles
• The combinatorial power of the companion matrix
• A proof of Golomb's conjecture for the de Bruijn graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Gray Code for Necklaces of Fixed Density
• Cycle decompositions of complete graphs
• 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)