d라이브러리

여러분이 이사를 한다고 가정해 봐요. 방에서 현관까지 아주 큰 물체, 예를 들어 침대나 피아노같은 아주 큰 가구를 옮겨야 해요. 이 가구가 다른 가구 또는 벽과 부딪히는 일 없이, 최소한의 힘으로 최소한의 길만 이동하려면 어떻게 해야 할까요?

언뜻 보면 생활 문제 같지만 이 문제를 수학적으로 증명한 알고리즘이 있어요! ‘피아노 이동 문제’라고 불리는 이 알고리즘은, 여러 개의 장애물이 있는 방에서 한쪽 모서리에 위치한 피아노를 다른 쪽으로 옮기는 방법을 계산해요. 장애물에 부딪히지 않고, 가장 일을 적게 하며 피아노를 옮길 수 있는 방법을 수학 공식과 컴퓨터 프로그래밍을 통해 찾는 거지요.

그냥 사람 눈으로 봐서 적당히 옮기면 되지 왜 알고리즘까지 짜냐고요? 피아노를 옮기는 것처럼 공간의 생김새에 맞춘 물체의 이동 경로를 계산하는 걸 ‘운동 계획 문제’라고 해요. 그리고 운동 계획 문제는 계산기하학에 속해요.

계산기하학은 기하학, 즉 물체나 공간을 다루는 학문에 대한 알고리즘을 연구하는 학문이에요. 도형을 가장 간단히 그리는 방법을 연구하거나 두 점을 잇는 가장 빠른 경로를 찾는 데 쓰인답니다. 앞에서 다룬 최단경로 찾기나 신장 트리 역시 넓게 보면 계산기하학에 속하지요.

운동 계획 문제는 산업용 로봇이 성장한 1970년대 말 이후 활발하게 연구됐어요. 왜냐하면 산업용 자율이동로봇이 이동하는 경로를 계산하는 데 이 알고리즘이 아주 유용했거든요.



자율이동 로봇은 스스로의 힘으로 정해진 경로만 다니도록 프로그래밍 돼요. 그런데 기계가 많은 공장 등에서 로봇이 이동할 경우, 다른 로봇이나 기계와 충돌할 위험이 있지요. 이를 피하기 위해 경로를 짜다 보면 비효율적으로 빙빙 돌아갈 수 있어요. 또 주어진 일을 정해진 장소에서 하기 위해서는, 시간과 일의 순서까지 생각해 전체 경로를 계산해야 하지요.

이때 여러 대의 로봇이 서로 충돌 없이 최단 거리를 이동할 수 있는 방법을 찾는 알고리즘을 짜면 매우 편리할 거예요. 3D 공간에서 계속 상상하며 경로를 그리는 것이 아니라, 컴퓨터 프로그래밍으로 만든 가상의 공간안에서 로봇의 이동 경로를 찾아내는 거지요. 이 공간에서 가상의 로봇은 몇 천 번, 몇 만 번씩 길을 계속 탐색하며 가장 좋은 경로를 발견할 수 있어요. 그것도 빠른 속도로요!

이처럼 운동 계획 문제는 작게는 집안의 가구를 옮기는 문제에서, 넓게는 무인 공장을 구성하는 방법에
까지 널리 쓰이고 있어요. 우주에 나가는 무인 탐사선이나 의료용 로봇의 움직임을 계산하는 데도 활약하고 있지요. 다시 말해 21세기 로봇 공학에서 꼭 필요한 알고리즘이랍니다.