비전공자도 이해할 수 있는 AI지식 -내비게이션이 최단거리를 찾는 방법-

1. 다익스트라, 최단거리를 탐색하게 해주다

 

강남역의 교통 체증 여부를 예측했으니, 이제 내비게이션으로 최적의 경로를 찾을 일만 남았습니다.

 

"강남역으로 안내해줘"라는 명령에 따라 내비게이션은 과연 어떻게 강남역까지 최적의 경로를 찾을 수 있을까요?

 

최단 경로를 찾는 알고리즘 중에서 가장 유명한 것은 아마 다익스트라 알고리즘(Dijkstra's Algorithm)일 것입니다.

 

네덜란드의 컴퓨터 과학자 에츠허르 데이크스트라가 대학원생이던 1956년 여자친구와 함께 커피숍에 갔다가 20분만에 고안해서 만든 알고리즘으로 알려져 있습니다.

 

커피숍에서 냅킨에 적을 수 있을 만큼, 단순한 법칙이 가장 뛰어나다는 오컴의 면도날을 증명하는 대표적인 알고리즘이기도 합니다.

 

 

 

물론 당시에 그는 이렇게 단순한 경로 계획 알고리즘이 미래에 수많은 분야에서 활용될지 전혀 상상도 못했겠지만요.

 

다익스트라 알고리즘은 현재 위치에서 주변을 모두 살핀 후 그 중 항상 최단 경로를 택하는 알고리즘입니다.

 

단순할 뿐만 아니라, 찾는 속도도 매우 빠릅니다.

 

성남에서 강남으로 가는 가장 빠른 경로를 찾는다고 해봅시다.

 

각 구간별 소요시간은 교통 정보를 반영하여 미리 계산되어 있습니다.

 

이제 가장 빠른 경로를 찾아나가면 됩니다.

 

먼저 출발지인 성남에서 갈 수 있는 모든 경로부터 살펴봅시다.

 

 

 

성남 > 판교, 성남 > 대치, 성남 > 복정 이렇게 3가지 선택지가 있습니다.

 

이 중 가장 짧은 시간이 걸리는 복정으로 이동해, 다시 복정 > 송파 까지 걸리는 시간을 더합니다.

 

 

 

그런데 성남 > 송파까지 걸리는 시간 16분에 비해, 성남 > 판교까지 6분이 걸리므로, 훨씬 더 짧은 시간이 소요됩니다.

 

그래서 이번에는 판교로 방향을 틀어 판교 > 청계산까지 걸리는 시간을 더해, 성남 > 청계산까지 소요 시간을 살펴봅니다.

 

 

 

이런 식으로 출발지인 성남을 중심으로, 가장 짧은 시간이 소요되는 위치를 계속해서 돌아보며 최종 도착지인 강남으로 향합니다.

 

여러 차례 다양한 방향으로 탐색을 거듭하며 총 9번의 시도 끝에 30분이 걸리는 성남 > 판교 > 청계산 > 양재 > 강남 경로를 찾아낼 수 있습니다.

 

 

 

그런데 이 알고리즘에는 문제가 있습니다.

 

너무 많은 경로를 탐색해야 한다는 거죠.

 

성남에서 강남까지 중간에 위치한 모든 구간을 탐색해야 합니다.

 

여기서도 탐색한 경로를 보면, 판교 방면으로 갔다가 잠실 방면으로 틀고, 다시 대치도 살펴보는 등, 

 

역삼을 제외한 모든 구간을 지나는 경로를 탐색한 후에야 강남까지 가는 최적 경로를 찾을 수 있었습니다.

 

이렇게 되면 실제로 내비게이션이 최적 경로를 탐색하는 데 너무 오랜 시간이 걸립니다.

 

예를 들어 서울에서 부산까지 가는 경로를 탐색한다고 해보죠.

 

그 사이에는 정말로 수많은 구간이 있기 때문에 최적 경로를 탐색하기 위해 이 모든 구간을 탐색하려면, 

 

아무리 고사양의 내비게이션이라도 수십분이 필요할겁니다.

 

경로 탐색에 수십분씩 걸리는 내비게이션을 이용할 고객은 아무도 없겠죠

 

이래서는 제대로 활용할 수가 없습니다.

 

요즘 나오는 내비게이션은 서울과 부산까지 최적 경로를 거의 실시간으로 찾아냅니다.

 

다익스트라 알고리즘으로는 이렇게 할 수가 없는데, 어떻게 이렇게 빠르게 찾아낼 수 있을까요?

 

 

2. A* 알고리즘, 실시간으로 최적 경로를 찾아내다

 

1968년 스탠퍼드연구소에서 A* 알고리즘을 개발합니다.

 

이 연구소는 이후 1970년에 스탠퍼드대학교에서 분리되었고, 1977년부터는 SRI 인터내셔널을 공식 명칭으로 사용하는데,

 

연구소 이름이 어딘가 낯익다면 여러분은 지금까지 책을 제대로 읽은 겁니다.

 

앞에서 살펴본 시리를 만든 곳이 바로 SRI 인터내셔널입니다.

 

시리가 만들어지기 40여년 전에 지금 모든 내비게이션이 채택한 알고리즘을 만들어냈습니다.

 

A* 알고리즘은 다익스트라 알고리즘의 확장판으로 볼 수 있는데,

 

거의 모든 경로를 탐색하던 다익스트라에 비해 꼭 필요한 경로만 탐색하여 탐색 횟수를 대폭 줄였습니다.

 

이게 가능한 이유는 출발지에서 도착지로 이동하는 시간뿐만 아니라 반대 방향,

 

즉 도착지에서 출발지로 거꾸로 이동하는 시간도 함께 계산에 포함하기 때문입니다.

 

이렇게 하면 애초에 도착지에서 먼 곳은 탐색할 시도조차 하지 않죠.

 

마치 알파고가 가능성이 높은 수 중심으로만 탐색하고, 나머지는 아예 탐색하지 않는 것과 비슷합니다.

 

A* 알고리즘은 이처럼 양방향 경로를 합산하여 최적 경로를 찾아냅니다.

 

 

 

이렇게 하면 성남에서 복정으로 향하는 구간은 딱 1번만 탐색하고 그 다음부터는 탐색하지 않습니다.

 

도착지에서 거꾸로 강남 > 복정 구간을 살펴봤더니, 애초에 오래 걸리는 경로이기 때문입니다.

 

다익스트라 알고리즘은 최단 경로를 찾기 위해 성남 > 복정 > 송파 > 잠실 > 삼성까지도 거슬러 올라갔지만, 

 

A*알고리즘은 이제 이 경로는 아예 탐색하지도 않습니다.

 

이렇게 하면 판교 방면으로 향하는 경로를 바로 택할 수 있고 단 4번만에 강남으로 향하는 최적 경로를 찾아낼 수 있습니다.

 

물론 중간에 대치로 빠지는 경로도 살짝 탐색해보긴 했지만, 이내 최적 경로를 찾아 강남까지 바로 탐색해냅니다.

 

이처럼 빠르게 계산할 수 있는 A*알고리즘은 내비게이션에 특히 유용합니다.

 

서울에서 부산까지 엄청나게 먼 거리도 불필요한 경로는 제외하여, 매우 빠르게 탐색할 수 있기 때문입니다.

 

또한 도착지에서 소요되는 시간뿐만 아니라 교통 지연, 도로 체증, 공사 여부, 신호등, 앞으로 남은 방향 전환 횟수 등 다양한 변수를 비용 함수로 정해 사용할 수도 있습니다.

 

심지어 직선거리도 활용할 수 있습니다.

 

예를 들어 A방향으로는 도착지까지 주행 경로가 50km인데 B방향은 도착지에서부터 직선거리만 해도 55km나 된다면, B방향은 굳이 탐색할 필요도 없는 거죠.

 

직선거리보다 더 짧은 경로는 없기 때문입니다.

 

또한 앞서 예측한 강남역의 교통 체증 여부도 A*알고리즘에 적용할 수 있습니다.

 

이처럼 A* 알고리즘에는 다양한 변수를 적용할 수 있기 때문에 활용도가 매우 높습니다.

 

그래서 사실상 시중에 있는 모든 내비게이션은 A* 알고리즘을 이용해 최적 경로를 계산한다고 할 수 있죠.

 

 

3. 경로만 잘 안내해준다고 내비게이션이 아니다

 

이처럼 최적 경로를 안내해주면 이제 내비게이션이 할 일은 모두 끝난 걸까요?

 

그렇지는 않습니다.

 

아무리 빠른 길이라도 많은 차량이 몰리면 그 길은 다시 정체 구간이 됩니다.

 

새로운 도로가 생겼다고 해서 항상 더 빨리 이동할 수 있는 것도 아닙니다.

 

새로 만든 도로에 차량들이 몰리면 교통 정체 상황이 도로 개통 이전보다 더욱 악화되는 경우가 있는데, 교통 분야에서는 이를 브라에스 역설이라고 합니다.

 

따라서 교통 시설 전체를 효율적으로 활용하려면 시간과 공간에 차량이 적절히 분포되어야 합니다.

 

아침 출근 시간대에 강남역에 교통 체증이 발생하는 이유도 동일한 시간대(출근 시간), 동일한 공간(강남역)에 차량이 몰리기 때문입니다.

 

실제로 명절에 티맵으로 교통 안내를 받던 차량들이 모두 국도로 몰리면서 오히려 국도에 극심한 정체가 발생한 일이 있을 정도입니다.

 

미국에서도 스마트폰 내비게이션앱인 웨이즈가 최적 경로라며 숨겨진 골목길을 안내해주는 바람에, 좁은 골목길에 갑자기 많은 차가 몰려 대혼란이 일어난 적이 있죠.

 

따라서 차량이 적절히 분산하도록 내비게이션은 모든 차량에 동일한 최적 경로를 제공하기보다, 

 

우회 경로를 포함한 다양한 경로를 제시할 필요가 있습니다.

 

물론 내비게이션이 전체 교통 상황을 고려해 특정 사용자에게 최적이 아닌 경로를 강제해도 되는지에 관해서는 여전히 논란의 여지가 있습니다.

 

마치 자율주행차가 보행자를 살리기 위해 탑승자를 희생하는 판단을 내려도 되는지와 비슷한 문제죠.

 

미국에서는 2017년 캘리포니아 대화재때, 내비게이션이 불이 난 도로로 안내해 큰 문제가 불거진 적이 있습니다.

 

물론 알고리즘이 사람을 해치기 위해 그런 행동을 한 건 결코 아닙니다.

 

단지 도로가 한산해 안내한 것뿐이었죠.

 

당시에는 도로에 불이 났다는 사실을 알고리즘이 알 수 있는 방법이 없었습니다.

 

이처럼 내비게이션이 풀어야 할 문제는 여전히 많이 남아있습니다.

 

이제 내비게이션 없이는 살아갈 수 없습니다.

 

그리고 내비게이션이 보다 더 똑똑해질 여지도 충분히 많이 남아있습니다.

 

내비게이션은 지금도 실시간 교통정보를 반영하고, 데이터를 끊임없이 주고받아 교통 상황을 분석하고,

 

빅데이터 정보도 반영하면서 훨씬 더 정교하게 최적 경로를 안내해주기 위해 끊임없이 개선되고 있습니다.

 

수많은 사람의 정보를 분석하고 시간과 요일, 날짜 등을 고려해 막힘 없이 원하는 목적지로 갈 수 있도록 예측 정보를 제공하고 최적의 경로로 우리를 매일 안내합니다.

 

내비게이션은 자율주행차에서도 매우 중요한 역할을 담당합니다.

 

정교한 지도를 기반으로 현재 위치를 파악하는 기능은 자율주행차가 스스로 목적지를 찾아서 주행을 하는 데 가장 핵심이 되는 기술이죠.

 

이처럼 내비게이션은 풀어야 할 숙제가 많은 동시에 앞으로의 역할 또한 기대가 되는 기술입니다.

 

내비게이션이 우리 곁에 본격적으로 등장한 지 이제 겨우 20년 남짓, 어느덧 내비게이션은 운전의 필수품으로 자리잡았습니다.

 

이제는 자율주행 시대를 맞아 미래 산업의 핵심기술로 자리매김할 것입니다.