AGV, 자율 주행차, 과연 가능할까?

구글 자율주행차 '사고 날 뻔한' 상황, 사람이 13차례 막아
http://news.naver.com/main/read.nhn?mode=LSD&mid=shm&sid1=105&oid=001&aid=0008116567

구글 자료에 따르면, 69회중 13회는 사람이 개입하지 않았다면 외부 물체와 부딪혔을 것으로 추정되며, 그중 3회는 상대방 차랑의 잘못이라고 하였다.

최근, IT 산업의 화두중 하나가, 자동차와 IT의 결합으로, 예를 들면, Apple car등이 될거 같다. 그만큼 관심을 많이 받고 있다는 점인데, 그런데, 만일, 모든 자동차가 자율 주행차라면, 어떤 현상이 발생하게될까?

현재 떠들석한 자율 주행차 보다 훨씬 이전, AGV(Automatic guided vehicles)라고, 이미, 몇십년전부터 자율 주행차는 연구가 되었었다. 그리고, 그 연구하는 사람중 하나가 필자였다(그리고, 머신러닝까지). 대략 생긴건 아래...

선진국의 항만등에서 사용되기도 하며, 작은 공장등에서도 쓰이기도 한다. 이런 AGV들이 Small한 땅에 뱅글배을 돌기 시작하면, 비용은 절감될 수 있겠지만, 그에 따른 이슈도 발생하기도 한다. 몇몇중 하나가 "혼잡도"이고, "Deadlock" 현상이다. 내가 주로 연구했던것이 "Deadlock"이였다.

"Deadlock"은 교착생태를 의미하는 것으로, A는 "사과"를 가지고 "배"를 원하고, B는 "배"를 가지고 "사과"를 원한다면 어떻게 될까? 둘다, 자신이 가진것을 손에 꼭쥔채, 양보없이 계속 시간만 흘러가는... 그런 현상이다.

이런 Deadlock은 A와 B간의 요구를 Link로 표시하는 Graph로 표현가능한데, Deadlock 특징은 위와 같이 Cycle이 발생하는 경우로 밝혀진다. 그런데, 이러한 Cycle detection은 NP-Hard 문제로, 풀수는 있지만, 계산량이 상당해진다.

단순히, A~G까지인데, 혹시, 그 사이에 Cycle이 있는지 찾아 보려면, 사람 조차도 손으로 몇번 따라가 봐야 한다. 만일, A~G까지, 7개가 아니라, 70만개가 된다면, 어떻게 될까? 컴퓨터의 계산으로 풀수 있을지는 모르지만, 개수 증가에 더욱 비례한 계산량에 의해, 실시간으로 답을 찾는것이 불가능할지 모른다.

왜 갑자기, Deadlock을 언급했는지는, AGV를 몇시간 Simulation해보면 알게 된다. 좁은 땅에, 자율 주행차를 몇대 주행시키다보면, 서로 가지 못해 부분 정체가 발생하게 되고, 그 부분 정체로 인해, 전체가 정채해버리는 현상이 발생하기 때문이다.

위 그림을 보면, 4대의 차가 서로 막힌것을 볼 수 있다. AGV라는 자율 주행차량은, 안전을 위해, 안전 거리를 미리 확보(즉, 점유)하고 지나가게 된다. 이 말인즉, A가 "사과"를 들고 있다는 것과 마찬가지 이다. 그런데, 4대의 차량이 각자 다른 차량이 점유한 영역을 서로 요청하게 된다면, 더이상 진행하지 못하고, "끽~"하고 멈춰버리는 현상이 발생하게 되는데, 이것이 바로 Deadlock의 발생이다. 위 그림을 참고하면 될것인데, 회색 부분이 각 차량이 현재 "안전 거리"를 위해 점유한 영역이 되며, 다음번 진행을 위해, 더 먼 거리를 요청하려고 하지만, 결국 서로 물려버려서, 진행을 못하게 되는 것이다.

문제는, 이들 4대의 차량이 멈춰버리면, 다른 차량도 같이 영향에 빠지게 된다는 점이다. 결국, 삽시간에, 그 일대의 전체 차량이 멈추게 된다. 그럼 조금 의자를 뒤로 당겨서, 멀리 볼까? 만일, 항만 같은 곳이 아닌, 전국을 무대로 이런 AGV 차량이 다닌다면, 한 부분의 정체는 결국 한 국가의 교통이 정체될 수 있음을 의미한다.

어떤가? 끔직하지 않은가? 전국의 차가 다 멈춰버린다는 현상이... 그런데, 사람은 왜 이런일이 발생하지 않을까? 바로, 사람은 적당 수준의 "양보"를 할 수 있기 때문이다. 사람이 위 4대의 차중 1대가 자신의 점유한 영역을 잠시 양보해서, 가만히 있다면, Cycle이 풀려, 3대의 차량은 1대씩 진행할 수 있게 된다. 그런데 왜 AGV는 그렇게 하지 못하는걸까? 바로, 자신이 Deadlock에 빠졌다는 것을 판단하는 것이 쉽지 않기 때문이다. 기계는 인위적인 "양보"를 할 수 없기 때문이기도 하다. 여하튼, 이런 Deadlock을 판단하는데는 엄청난 계산량이 필요하다(사실, 엄청난것이라기 보다는 계산량이 많다는 점이다. 차량이 4대인것과 차량이 4억대라고 하는것, 4억대중, 어떤 4대가 cycle에 빠졌다는것을 찾는건, 실시간 계산으로는 쉽지 않다).

그래서, 나는 일찌감치, "자율 주행차"는 "불가능"한 영역이라 생각했었는데, 최근에 자주 언론에 공개되는걸로 봐선, "가능할까?" 의문이 들기도 하였다. 구글같이, 한두대정도 넓은 도로를 달리는것은 아무런 문제가 없겠지만, 만일, 10만대정도의 차량이 자율로 임의의 도시에 달린다고 한다면, 분명 deadlock 현상은 발생하게 될 것이며, 결국 "수동모드"를 통해 사람이 직접 개입해야 할 것이다. 뭐,... 이런것까진 언론에 잘 공개되진 않는듯 하다.