×

Partitioning de Bruijn graphs into fixed-length cycles for robot identification and tracking. (English) Zbl 1344.05114

Summary: 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 \(\operatorname{dB}(q,\ell)\).
We provide several existence results that give the maximum number of cycles in \(\operatorname{dB}(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 \(\operatorname{dB}(q,\ell)\) can be partitioned into \(k\)-cycles, then \(\operatorname{dB}(q,t\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.

MSC:

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

References:

[1] Alspach, B.; Gavlas, H.; Šajna, M.; Verrall, H., Cycle decompositions. IV. Complete directed graphs and fixed length directed cycles, J. Combin. Theory Ser. A, 103, 1, 165-208 (2003) · Zbl 1022.05061
[2] Anderson, B. D.O.; Yu, C.; Fidan, B.; Hendrickx, J. M., Rigid graph control architectures for autonomous formations: applying classical graph theory to the control of multiagent systems, IEEE Control Syst. Mag., 28, 6, 48-63 (2008) · Zbl 1395.93383
[3] Bryant, D. E., Decompositions of directed graphs with loops and related algebras, Ars Combin., 38, 129-136 (1994) · Zbl 0824.05050
[4] Bryant, D., Cycle decompositions of complete graphs, (Surveys in Combinatorics 2007. Surveys in Combinatorics 2007, Ser. London Math. Soc. Lecture Note Ser., vol. 346 (2007), Cambridge Univ. Press), 67-97 · Zbl 1131.05070
[5] Bryant, D.; Horsley, D.; Pettersson, W., Cycle decompositions V: Complete graphs into cycles of arbitrary lengths, Proc. Lond. Math. Soc. (3), 108, 5, 1153-1192 (2014) · Zbl 1296.05044
[6] Chen, W. Y.C.; Louck, J. D., The combinatorial power of the companion matrix, Linear Algebra Appl., 232, 261-278 (1996) · Zbl 0838.15015
[7] Cohn, M.; Lempel, A., Cycle decomposition by disjoint transpositions, J. Combin. Theory Ser. A, 13, 83-89 (1972) · Zbl 0314.05005
[8] d’Ademo, N.; Lui, W. L.D.; Li, W. H.; Şekercioğlu, Y. A.; Drummond, T., eBug—an open robotics platform for teaching and research, (Australasian Conference on Robotics and Automation (2011), Australian Robotics & Automation Association)
[9] Das, A. K.; Fierro, R.; Kumar, V.; Ostrowski, J. P.; Spletzer, J.; Taylor, C. J., A vision-based formation control framework, IEEE Trans. Robot. Autom., 18, 5, 813-825 (2002)
[10] de Bruijn, N. G., A combinatorial problem, Nederl. Akad. Wetensch., Proc., 49, 758-764 (1946) · Zbl 0060.02701
[12] Erdős, P.; Lovász, L., Problems and results on 3-chromatic hypergraphs and some related questions, (Infinite and Finite Sets. Infinite and Finite Sets, Ser. Colloq. Math. Soc. János Bolyai, vol. 10 (1975), North-Holland), 609-627
[13] Fraleigh, J.; Katz, V., (A First Course in Abstract Algebra. A First Course in Abstract Algebra, Ser. Addison-Wesley World Student Series (2003), Addison-Wesley)
[14] Fredricksen, H., The lexicographically least de Bruijn cycle, J. Combin. Theory, 9, 1-5 (1970) · Zbl 0199.31702
[15] Good, I. J., Normal recurring decimals, J. Lond. Math. Soc., 21, 167-169 (1946) · Zbl 0060.02702
[16] Kobayashi, M.; Kiyasu-Zen’iti; Nakamura, G., A solution of Dudeney’s round table problem for an even number of people, J. Combin. Theory Ser. A, 63, 1, 26-42 (1993) · Zbl 0783.05033
[17] Kobayashi, M.; Nakamura, G., Resolvable coverings of 2-paths by cycles, Graphs Combin., 18, 4, 739-744 (2002), graph theory and discrete geometry (Manila, 2001) · Zbl 1009.05037
[18] Moreau, C., Sur les permutations circulaires distinctes, (Nouvelles Annales De Mathématiques, Vol. 11 (1872), Gauthier-Villars), 309-314 · JFM 04.0086.01
[19] Mykkeltveit, J., A proof of Golomb’s conjecture for the de Bruijn graph, J. Combin. Theory Ser. B, 13, 40-45 (1972) · Zbl 0221.05068
[20] Nakamura, G.; Kiyasu, Z.; Ikeno, N., Solution of the round table problem for the case of \((p^k + 1)\) persons, Comment. Math. Univ. St. Paul., 29, 1, 7-20 (1980) · Zbl 0435.05001
[22] Savage, C., A survey of combinatorial Gray codes, SIAM Rev., 39, 4, 605-629 (1997) · Zbl 1049.94513
[23] Spencer, J., Asymptotic lower bounds for Ramsey functions, Discrete Math., 20, 1, 69-76 (1977/78) · Zbl 0375.05033
[24] van Aardenne-Ehrenfest, T.; de Bruijn, N. G., Circuits and trees in oriented linear graphs, Simon Stevin, 28, 203-217 (1951) · Zbl 0044.38201
[25] Wang, T. M.Y.; Savage, C. D., A Gray code for necklaces of fixed density, SIAM J. Discrete Math., 9, 4, 654-673 (1996) · Zbl 0866.05036
[26] Wang, X.; Şekercioğlu, Y. A.; Drummond, T., Vision-based cooperative pose estimation for localization in multi-robot systems equipped with RGB-D cameras, Robotics, 4, 1, 1-22 (2015), special issue on coordination of robotic systems
[29] Zhang, F. J.; Lin, G. N., On the de Bruijn-good graphs, Acta Math. Sinica, 30, 2, 195-205 (1987) · Zbl 0628.05047
[30] Zsigmondy, K., Zur theorie der potenzreste, Monatsh. Math. Phys., 3, 1, 265-284 (1892) · JFM 24.0176.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.