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

详细信息    查看全文

• 作者：Tony Grubman^a ; ^b ; ^{tony.grubman@monash.edu" class="auth_mail" title="E-mail the corresponding author} ; Y. Ahmet Şekercioğlu^a ; ^c ; ^{asekerci@utc.fr" class="auth_mail" title="E-mail the corresponding author} ; David R. Wood^b ; ^{david.wood@monash.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph theory ; Robot network ; de Bruijn graph ; Graph decomposition ; Pose estimation ; Linear feedback shift register
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 November 2016
• 年：2016
• 卷：213
• 期：Complete
• 页码：101-113
• 全文大小：1076 K

文摘

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$q$, the number of lights on each robot, k$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$k$-cycles in the de Bruijn graph dB(q,ℓ)$dB(q,\ell )$.

We provide several existence results that give the maximum number of cycles in dB(q,ℓ)$dB(q,\ell )$ in various cases. For example, we give an optimal solution when k=q^ℓ−1$k=q^{\ell -1}$. Another construction yields many cycles in larger de Bruijn graphs using cycles from smaller de Bruijn graphs: if dB(q,ℓ)$dB(q,\ell )$ can be partitioned into k$k$-cycles, then dB(q,tℓ)$dB(q,t\ell )$ can be partitioned into tk$tk$-cycles for any divisor t$t$ of k$k$. The methods used are based on finite field algebra and the combinatorics of words.