슬라이딩 스퀘어의 분산형 마름모 형성
슬라이딩 스퀘어 모델은 로봇 모듈의 자가 재구성 연구에 널리 활용되는 추상화 모델입니다. 본 연구는 임의의 측면 연결 구성에서 시작하여 모듈 그룹이 마름모 형태로 재구성되도록 하는 새로운 분산 알고리즘을 제안합니다. 이 알고리즘은 연결성을 보존하며, 단일 리더 모듈, 공통 카이랄성, 모듈당 상수 메모리, 그리고 인접 모듈에 대한 가시성 및 통신 제한이라는 최소한의 가정 하에 작동합니다. 기존 연구들이 슬라이딩 스퀘어의 이동 규칙을 완화했던 것과 달리, 본 접근 방식은 수정되지 않은 이동 규칙을 사용합니다. 이는 어떤 모듈도 마름모 내 목표 위치까지 연결성을 보존하는 경로를 갖지 못하는 구성에 대한 추가적인 난제를 해결합니다. 제안된 순차 알고리즘은 최악의 경우 O(n^2) 라운드의 시간 복잡도를 가지며, 이는 순차 알고리즘으로는 최적입니다. 실행 시간 개선을 위해 두 가지 병렬 변형 알고리즘을 도입했습니다. 이들은 모두 스패닝 트리 데이터 구조를 활용하여 모듈이 지역 연결성을 기반으로 의사결정을 내리도록 합니다. 실험 결과, 첫 번째 변형은 상당한 속도 향상을 보였으며, 두 번째 변형은 병렬 알고리즘에서 최악의 경우 최적인 선형 평균 실행 시간을 달성했습니다. 본 연구는 자가 재구성 로봇 시스템의 효율적인 형태 형성 문제에 대한 실용적인 해결책을 제시하며, 특히 제한된 자원 및 통신 환경에서의 로봇 협업 전략 개발에 기여할 수 있습니다.