A Construction of Connected Dominating Set with Predetermined Nodes and Vision-based Formation control with Control Barrier Function

Abstract

이 논문은 분산 알고리즘에 대한 두 가지 주요 주제를 다룬다. 첫 번째 주제는 무선 애드혹 네트워크에서의 문제를 다루며, 특히 연결 지배 집합(CDS)을 가상 백본 네트워크로 구성하는 데 중점을 둔다. 기존 연구들이 모든 노드가 균일한 자격을 갖춘 것으로 가정한 반면, 본 논문은 고유한 특성으로 인해 CDS에 포함되거나 제외되어야 하는 특정 노드가 사전에 결정된 상황을 고려한다. 이를 바탕으로 강제-CDS 문제를 정의하고, 사전 결정된 노드를 포함하는 CDS 구성 문제로 확장하였다. 또한 기존의 2홉 접근 방식을 넘어, 1홉 정보를 활용한 중앙 집중식 및 분산식 알고리즘을 새롭게 제안하였다.

두 번째 주제는 로봇 간 통신에 의존하지 않고 가시성 제약 조건하에서 작동하는 비홀로노믹 이동 로봇을 위한 비전 기반 편대 제어 알고리즘이다. 선행 에이전트를 추적하는 데 사용되는 카메라가 시야각 제한을 가지므로, 효과적인 추적을 위해 실시간 가시성을 유지하는 것이 중요하다. 이를 해결하기 위해 카메라의 픽셀 좌표를 기반으로 한 배리어 함수를 설계하였고, 이 함수를 제약 조건으로 활용하는 이차 최적화 기반 제어기를 통해 가시성 유지와 비홀로노믹 특성을 동시에 만족시킬 수 있음을 입증하였다. 제안된 방법의 유효성은 시뮬레이션을 통해 가시성을 유지하면서 원하는 편대 형상을 달성하는 성능을 확인함으로써 검증하였다. ©2025 원승범 ALL RIGHTS RESERVED|This dissertation addresses two topics about distributed algorithms and is divided into two parts. The first part addresses the challenges in wireless ad-hoc networks, particularly focusing on the construction of a Connected Dominating Set (CDS) as a virtual backbone network. Unlike previous works that assume uniform qualifications for all nodes, we consider cases with predetermined nodes that must be either included in or excluded from the CDS due to their unique functionalities. In this context, we extend the Enforced-CDS problem to a CDS construction problem with predetermined nodes. Contribution includes the development of both centralized and distributed algorithms that utilize one-hop information, diverging from the traditional two-hop approach. The size of the computed CDS by the proposed algorithms does not exceed 6.798 times the optimum.

The second part explores a vision-based formation control algorithm for nonholonomic mobile robots operating under visibility constraints without relying on inter-robot communication. The camera used to monitor the leading agent has field of view (FOV) constraints, making it crucial to maintain real-time visibility for effective leading agent tracking. To address these challenges, we designed a barrier function based on the camera's pixel coordinates and showed that the control barrier function based quadratic programming satisfies both the visibility maintenance and nonholonomic property. The effectiveness of the proposed method is validated through simulations that demonstrate its ability to maintain visibility and achieve the desired formation. ©2025 Seung-Beom Won ALL RIGHTS RESERVED