다이나믹 프로그래밍(=동적 계획법)의 기본적인 아이디어는 하나의 복잡한 문제를 간단한 하위 문제 여러 개로 나누어 해결하는 알고리즘 기법이다. 각 하위 문제의 해결 방법을 저장하고, 동일한 하위 문제가 발생했을 때 이를 다시 계산하지 않고 저장된 값을 활용함으로써 효율적으로 문제를 해결할 수 있다.

동적 계획법은 하나의 문제를 여러 개의 하위 문제로 나누어 해결한다는 접에서 분할 정복(Divide and Conquer)과 유사하다. 그러나 동적 계획법은 분할된 부분문제들끼리 서로 의존적이지만 분할 정복은 부분문제들끼리 서로 독립적이라는 차이점을 갖는다.

DP 적용 조건

다이나믹 프로그래밍을 적용할 수 있는 상황에 대한 조건은 다음과 같다.

1. 최적 부분구조 (Optimal Substructure) : 부분 문제의 최적 값을 통해 전체 문제의 최적 값을 도출할 수 있는 구조
2. 중복되는 부분문제 (Overlapping Subproblems) : 전체 문제를 해결함에 있어 동일한 부분 문제가 중복되어 발생하는 문제

예제) 피보나치 문제

대표적으로 피보나치 문제에 DP를 적용할 수 있다.

1. 재귀적 방법

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

점화식처럼 관계식이 주어져있기 때문에 재귀로 구현할 수 있다.

재귀적 방법으로 f(5)를 구할 때, f(4)와 f(3)을 계산해야 한다. 이 때 f(4)를 구하기 위해서는 다시 f(3)과 f(2)를 계산해야 한다. 이 때 f(3)은 이전에 계산되었기 때문에 다시 계산할 필요가 없지만 재귀적 방법에서는 이를 고려하지 않고 모든 하위 문제를 매번 다시 계산하게 된다. 이로 인해 중복 계산이 발생해 불필요한 연산 횟수가 많아지게 된다.

재귀적 방법으로 구현 시 f(n)을 위해 O(2^n)의 시간 복잡도를 가지며, 이는 n값에 비례해 연산량이 급격히 증가함을 확인할 수 있다.

2. 동적 계획법

f(n)은 f(n-1)과 f(n-2)의 합으로 구성되어 최적 부분구조 조건(부분문제의 값만으로 전체문제의 값을 구할 수 있음)을 만족한다.

또한 f(5)를 구하기 위해 위 그림과 같이 f(4), f(3), .., f(0)의 똑같은 부분문제가 계속 발생됨을 알 수 있다. 즉 중복되는 부분문제를 만족한다.

def fibonacci(n):
    fib = [0] * (n+1)
    fib[1] = 1
    for i in range(2, n+1):
        fib[i] = fib[i-1] + fib[i-2]
    return fib[n]

따라서 동적 계획법을 위한 조건이 성립되어 적용해 구현할 수 있다. 반복문을 통해 각 항의 값을 저장하면서 이전 값들을 활용해 새로운 값을 계산하여 중복 계산을 피하고, 이전에 계산된 값을 재활용함으로써 효율적으로 연산할 수 있다.

일반적으로 DP 적용 시 부분문제의 값을 알고 있을 때 O(1)이 소요되며, 모든 부분문제의 개수는 n이므로 O(n)의 시간 복잡도를 갖는다.

DP 적용

동적 계획법은 어떤 특정 경우에만 적용되는 것이 아닌 다양한 문제 해결에 적용할 수 있는 알고리즘이기에 풀고자 하는 문제가 동적 계획법을 사용할 수 있는 문제인지 확인하는 과정이 필요하다.

먼저 앞선 최적 부분구조/중복되는 부분문제 조건을 만족하여야 한다. 그리고 문제에서 사용할 변수에 대해 정의하고 변수 간 관계식(점화식)을 수립한다. 이후 계산될 때마다 배열에 값을 저장하고 이를 재사용하는 방식으로 문제를 해결한다.

구현 방법은 크게 상향식과 하향식, 두 방법으로 나뉜다.

1. 상향식 방법 (Bottom-up, Tabulation) - 반복문 사용 작은 문제에서 시작해 누적시켜 점진적으로 큰 문제를 해결하는 방식이다. 결과를 저장한 배열 dp[0]에서 시작해 목표인 dp[n]에 이르기까지 값을 저장하며 이를 재활용하며 진행된다.

2. 하향식 방법 (Top-down, Memoization) - 재귀 사용 dp[0]처럼 처음부터 출발하는 게 아닌 dp[n]을 구하기 위해 위에서 시작해 dp[0]까지 내려간 다음 결과 값을 재귀를 통해 재활용하는 방식이다. 큰 문제를 해결할 때 부분문제가 해결되지 않았다면 그제서야 해결하게 된다.

트리(Tree)는 계층적인 구조를 표현하는 자료구조로, 노드(node)들이 간선(edge)으로 연결된 형태를 가지며 하나의 루트(root) 노드를 가진다. 트리는 컴퓨터 과학에서 매우 중요한 자료구조로 다양한 응용 분야에서 활용된다.

트리의 구조

• 루트 노드 : 트리의 최상위에 위치하는 노드로, 모든 경로의 시작점
• 부모-자식 관계 : 각 노드는 부모-자식 관계를 가지며, 부모 노드에서 자식 노드로의 방향성을 가짐
• 계층 구조 : 노드들은 부모와 자식 관계를 통해 계층적으로 구성됨
• 리프 노드 : 자식이 없는 노드로, 트리의 가장 하위에 위치

용어

• 노드(Node) : 트리를 구성하는 기본 요소로, 계층구조를 형성하며 서로 연결됨
• 간선(Edge) : 노드와 노드를 연결하는 선
• 루트(Root) : 트리의 최상위 노드
• 부모(Parent) : 어떤 노드의 바로 위에 있는 노드
• 자식(Children) : 어떤 노드의 바로 아래에 있는 노드
• 조상(Ancestor) : 특정 노드에서 루트까지의 경로 상에 있는 모든 노드들
• 자손(Descendant) : 특정 노드에서 해당 노드까지의 경로 상에 있는 모든 노드들
• 형제(Sibling) : 같은 부모를 가지는 노드들
• 높이(Height) : 트리의 최대 레벨 수
• 깊이(Depth) : 특정 노드에서 루트까지의 경로의 길이

특성

1. 계층 구조 : 트리는 부모-자식 관계를 가진 노드들로 이루어진 계층적인 구조로, 각 노드는 자신의 부모와 자식 노드를 가지고 이러한 구조는 데이터의 계층화를 효과적으로 표현할 수 있다.

2. 단일 경로 : 트리에서 두 노드를 연결하는 경로는 유일하다. 부모 노드에서 자식 노드로든 가는 경로는 오직 한 가지로, 그 연결선이 edge가 된다.

3. 비순환적 구조 : 트리의 어떤 경로를 따라가도 동일한 노드를 두 번 이상 방문하지 않는다.

4. 유일한 루트 노드 : 모든 트리는 단 하나의 루트 노드를 가진다. 루트 노드는 트리의 시작점이며, 모든 다른 노드는 루트 노드로부터의 어떠한 경로를 통해 접근 가능하다.

5. 서브 트리(Subtree) : 트리 내의 어떤 노드와 그 자손들로 이루어진 부분 트리로, 어떤 노드를 루트로 하는 서브 트리는 그 노드의 자식들과 그 자식들의 자손들로 이루어진다.

트리의 종류

이진 트리 (Binary Tree)

이진 트리는 노드들이 최대 두 개의 자식을 가지며, 루트 노드를 시작으로 각 노드들이 서로 연결된 구조의 트리를 말한다. 최대 두 개의 자식을 가지므로 자식이 없을 수도, 1개만 가질 수도 있다. 이진 트리 중 구조와 특징에 따라 완전 이진트리, 편향 이진트리, 포화 이진트리 등으로 분류될 수 있다. 다음은 흔히 사용되는 이진 트리의 일종이다.

이진 탐색트리 (Binary Search Tree)

이진 탐색 트리(Binary Search Tree)는 이진 트리의 일종으로, 다음 조건을 만족하는 트리이다.

1. 왼쪽 서브트리의 모든 노드들의 값은 해당 노드의 값보다 작다.
2. 오른쪽 서브트리의 모든 노드들의 값은 해당 노드의 값보다 크다.
3. 모든 노드의 왼쪽, 오른쪽 서브트리 모두 이진 탐색 트리를 만족한다.

이런 특성을 활용해 재귀적으로 트리를 순회하여 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행할 수 있고 데이터를 정렬된 상태로 유지할 수 있다. BST의 탐색 연산은 평균적으로 O(log n)의 시간복잡도를 가지므로 효율적으로 수행된다고 볼 수 있다. 최악의 경우(편향된 트리일 경우) O(n)의 시간복잡도를 가질 수 있다.

힙 (Heap)

힙(Heap)은 완전 이진트리(마지막 레벨을 제외한 모든 레벨이 가득 채워져 있으며 마지막 레벨 노드들이 왼쪽부터 순차적으로 채워진 트리)를 만족하며, 왼쪽 자식은 해당 노드보다 작은 값을, 오른쪽 자식은 해당 노드보다 큰 값을 가지는 조건을 만족한다. 최대 힙(MaxHeap) 은 부모 노드의 값이 자식 노드의 값보다 크거나 같으며, 최소 힙(MinHeap) 은 부모 노드의 값이 자식 노드의 값보다 작거나 같다.

기존 배열에서 최대/최소값을 찾기 위해서는 O(n)이 소요되지만 힙에서는 O(logn)만큼 소요되는, 주어진 데이터에서 최대/최소값을 빠르게 찾기 위해 고안된 이진 트리이다.

Binary Search Tree vs Heap

힙과 BST 모두 이진 트리의 일종이기 때문에 헷갈릴 수 있지만 목적과 동작 방식에 있어 차이를 가진다.

• BST는 탐색 연산에 중점을 둔 자료구조로, 기준 노드를 기준으로 왼쪽 서브트리는 모두 작고 오른쪽 서브트리는 모두 큰 값을 가진 노드들이 존재하기에 이를 활용해 탐색을 수행한다. 하지만 힙은 최대/최소값에 빠르게 접근하기 위한 자료구조로, 루트 노드가 목표로 하는 최대/최소값이므로 이에 접근할 수 있다.
• 힙은 BST와 달리 왼쪽/오른쪽 서브트리가 기준 노드보다 모두 작거나/큰 성질을 만족하지 않는다. 단순히 부모-자식 간의 관계에서 최대힙/최소힙 성질만을 만족한다.

AVL 트리

AVL 트리는 자가 균형 이진 탐색 트리로, 스스로 균형을 유지하는 트리 구조이다. 위의 BST 자료처럼 이진 탐색 트리에서 데이터가 편향된 경우, 즉 한 쪽으로 치우쳐진 경우 탐색에 O(n)의 시간이 소요될 수 있다. 이렇게 편향된 이진 트리는 트리의 높이가 높아져 탐색에 오랜 시간이 소요되는데, AVL 트리에서는 이를 방지하기 위해 균형을 유지하고자 한다.

AVL 트리는 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 최대한 작게 유지하여 균형을 유지한다. 이를 통해 탐색, 삽입, 삭제 연산에 대해 항상 O(log n)의 시간 복잡도를 유지할 수 있다. AVL 트리는 다음 요소들을 통해 균형을 유지한다.

• Balance Factor : 각 노드의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이를 의미한다. 각 노드의 Balance Factor는 -1, 0, 1이어야 한다.
• 회전(Rotation) : 균형을 유지하기 위해 회전 연산을 사용하는데 LL(Left-Left), RR(Right-Right), LR(Left-Right), RL(Right-Left) 회전이 있다. 이러한 회전을 통해 균형을 재조정한다.

레드-블랙 트리(Red-Black Tree)

레드-블랙 트리도 자가 균형 이진 탐색 트리로, 모든 노드는 'Red' or 'Black' 색상을 가지며 루트 노드는 Black이고 빨간색 노드는 연속으로 올 수 없다는 규칙을 만족한다.

1. 모든 노드는 빨강 or 검정이다
2. 루트 노드는 항상 검정이다
3. 모든 null 노드(leaf)는 검정이다
4. 빨강 노드는 연속으로 존재할 수 없다
5. 임의의 노드에서 자손 null 노드로 가는 경로들의 검정 노드 수는 같다 (=black height)

레드-블랙트리는 편향된 이진 탐색트리를 개선한 구조로 rotation과 re-coloring을 통해 균형을 유지하며 최악의 경우에도 O(logn)의 시간복잡도를 가진다. 따라서 실시간 처리처럼 실행시간이 중요한 경우 주로 사용된다.

AVL 트리 vs 레드-블랙 트리

둘 다 자가 균형 이진 탐색 트리이지만, 균형을 잡는 과정에서 레드-블랙 트리에 비해 AVL 트리에서 회전 연산이 더 많이 발생할 수 있다. 레드-블랙 트리는 노드의 색상을 조정하며 균형을 유지하므로 회전이 발생하지 않을 수도 있어 AVL 트리의 균형 조건이 더 엄격한 편이다.

더욱 엄격한 균형 조건의 AVL 트리는 검색 성능이 더 우수할 수 있고 레드-블랙 트리는 삽입/삭제 연산에 더 효율적인 특징을 갖는다.

자율주행 인지 단계는 자율주행 차량이 주변 환경을 이해하고 파악하는 단계로, 다양한 센서들을 활용해 주변 환경을 감지하고 이해하는 과정이 이루어진다. 구체적으로 객체를 검출하여 인식하고, 인식한 객체의 움직임을 추적/예측하는 모든 과정이 포함된다.

동적 객체 검출/추적, 예측

동적 객체라 하면 시간에 따라 움직임을 갖는 객체로, 주변 차량이나 보행자 등을 의미한다. 인지 단계에서는 동적 객체에 대해 인식하여 어떤 객체인지 판별하고 기준 차량으로부터의 거리 등을 계산해 객체를 검출한다. 검출한 객체를 대상으로 t 시점 해당 객체와 t+1 시점의 객체를 연결지어 객체를 추적한다.

이렇게 추적한 동적 객체의 tracking을 바탕으로 분석하여 해당 객체가 미래에 어떻게 움직일 것인지를 예측한다. 이를 바탕으로 자율주행의 판단 및 계획을 수립할 수 있다.

정적 객체 인식

정적 객체라면 시간에 따라 움직이지 않는 객체로, 신호등과 표지판, 횡단보도 등을 말한다. 인지 단계에서 이런 정적 객체의 종류와 위치를 파악하여 인식한다. 인식된 상황을 바탕으로 주행을 하도록 하거나 정밀지도 제작에 기여할 수 있다.

자율주행 센서 구성

자율주행을 위한 대표적인 센서는 다음과 같다.

카메라

주변 환경의 광학적 이미지를 전기적 신호로 변환하는 장치로, 빛이 렌즈를 통해 들어오면 이미지 센서(CCD, CMOS)를 통해 빛의 강도와 색을 전기적 신호로 변환하여 2차원 배열로 저장

• ↑ : 고해상도 이미지 제공, 비교적 저렴한 가격
• ↓ : 고해상도 이미지에 따른 많은 계산량, 외부 요인에 민감

레이다 (RADAR)

전자기파(마이크로파)를 발사하여 반사파를 분석함으로써 객체의 위치, 속도를 파악

• ↑ : 외부 요인에 강인, 비교적 저렴한 가격
• ↓ : 주변 환경의 반사 신호로 인해 간섭(클러터)으로 오탐률, 낮은 해상도

라이다 (LIDAR)

레이저 펄스를 주변으로 발사해 객체에 반사되어 되돌아오는 시간을 측정해 거리를 계산하여 객체의 위치, 모양, 크기를 파악

• ↑ : 정밀한 측정 가능, 외부 요인에 강인
• ↓ : 비싼 가격, 습기가 있을 경우 산란되어 성능 저하

센서 퓨전

위 각각의 센서는 고유의 한계를 가진다. 예를 들어 카메라는 조명이나 반사로 인해 정보가 왜곡될 수 있고, 레이다는 날씨 조건에 강하지만 낮은 해상도를 갖고, 라이다는 고해상도 거리 측정에 유리하지만 높은 비용을 수반한다.

따라서 여러 센서로부터 얻은 데이터를 통합해 사용하는 센서 퓨전(Sensor Fusion)을 통해 보다 정확한 수 있는 정보를 생성할 수 있다. 센서 퓨전은 크게 세 가지 수준으로 분류될 수 있다.

1. Low-level Fusion : 여러 센서로부터 얻은 데이터를 직접 통합한다. 복잡한 알고리즘의 필요 없이 단순한 통합으로 실시간 처리에 유리하지만 데이터 중복과 병합의 문제를 갖는다.
2. Feature-level Fusion : 각 센서의 특징이 추출되고 이러한 특징들이 결합되어 더 유용한 정보를 생성한다. 더 복잡하고 효율적인 데이터 처리가 가능하며 센서에서 추출된 특징들의 결합으로 높은 신뢰성을 갖는다.
3. Decision-level Fusion : 각 센서에서 독립적으로 내린 의사결정(객체 식별 등)을 통합하여 최종 의사결정을 내린다. 각 센서의 특성을 고려하여 보다 강력한 의사 결정을 할 수 있지만 통합 과정에서 복잡한 로직이 요구될 수 있다.

인지 기술의 과제

대부분의 자율주행 차량에서 발생한 사고에서, 정확한 인지 작업이 되지 않아 발생한다. 예측하기 힘든 다양한 도로 환경에 대해 여러 인지 오작동 발생 시 자율주행의 모든 프로세스가 무력화되어 사고가 발생하기 때문에 100%에 가까운 정확도를 필요로 한다.

• 다양한 환경 조건에서도 안정적으로 작동할 수 있는 센서 기술과 함께 센서 데이터를 보정/최적화하는 알고리즘 개발
• 동적 환경에서도 정확한 인식과 예측을 위해 딥러닝 기반 고급 인지 알고리즘 개발
• 효율적인 센서 퓨전 기술 개발

딥러닝 활용

CNN (Convolutional Neureal Network)

CNN은 다층 구조를 통해 여러 계층에서 이미지의 다양한 특징을 계층적으로 학습할 수 있어 특히 이미지 인식 및 이해에 있어 강점을 갖는 신경망이다. 자율주행 환경에서 카메라 영상을 입력으로 하여 공간적 이미지의 특징을 추출함으로써 목적에 맞게 사용할 수 있다. 따라서 CNN을 인지 기술에서 활용하는 예는 다음과 같다.

• 객체 인식, 분류 : 주변 환경에서 동적, 정적 객체의 다양한 객체를 인식하고 분류할 수 있다. YOLO(You Only Look Once), SSD(Single Shot MultiBox Detector)는 실시간 객체 감지를 위해 흔히 사용되는 신경망 아키텍쳐이다.
• 차선 검출 : 입력 이미지에서 차선의 형태와 경계를 인식할 수 있다.
• 환경 인지 및 3D 매핑 : 공간적 특징을 추출해 주변 환경의 3D 구조를 재구성하여 주변 환경을 정확히 이해할 수 있도록 한다.

RNN (Recurrent Neural Network)

RNN은 순환 구조를 갖고 있어 순차적인 데이터나 시계열 데이터를 처리하는 데 특히 효과적인 신경망으로, 이러한 특성을 활용하여 자율주행에서 다양한 응용이 가능하다.

• 주행 경로 예측 : 차량 위치, 속력, 주변 차량의 위치와 같은 시계열 데이터를 입력으로 받아 패턴을 학습하고, 이전 시간 단계의 정보를 현재 시간 단계의 예측에 활용하여 주행 경로 예측에 활용된다.

LSTM (Long Short Term Memory)

전통적인 RNN에서는 입력 시퀀스 길이가 길어지면 시간에 따라 장기 의존성(Long-Term Dependencies)으로 인해 학습이 제대로 되지 않아 이를 해결하기 위해 LSTM이 개발되었다.

LSTM은 위와 같이 두 벡터(Ct : Cell state, ht : hidden state)와 3개의 게이트(input, forget, output gate)를 갖는다. 다음은 각 요소에 대한 설명이다.

• Cell state : 셀 상태는 LSTM의 핵심 메모리 부분으로, 장기적인 정보를 저장하고 전달한다. Gate 메커니즘에 의해 업데이트된다.
• hidden stae : 현재 시점 단계의 출력으로 사용된다. LSTM은 입력 x(t)와 h(t-1)를 기반으로 h(t)를 계산한다. 이는 다시 t+1 단계의 입력으로 사용된다.
• Input gate : 현재 시점 단계의 입력에 대한 가중치를 결정 (이번 입력을 얼마나 반영할지)
• Forget gate : 이전 셀 상태에서 어떤 정보를 정보를 망각할지 결정하여 불필요한 정보 제거 (과거 정보를 얼마나 까먹을지)
• Output gate : 다음 시점 단계의 hidden state에 대해 가중치를 결정하여 다음 단계로 전달 (이번 정보를 얼마나 내보낼지)

측위 기술

측위 기술은 자율주행 차량이 현재 위치를 정확하게 파악하는 데 사용된다. 측위 정보를 활용해 센서가 감지하는 정보를 보완할 수 있다.

GPS (Global Positioning System)

GPS는 위성을 통해 전 세계적으로 정확한 위치 정보를 제공하는 인공위성 네비게이션 시스템으로, 전파 상황에 따라 정밀도가 좌우되고 위치 오차가 미터 단위이기 때문에 자율주행에 직접적으로 활용하기는 어렵다.

GNSS (Global Navigation Satellite System)

GNSS는 GPS뿐만 아니라 GLONASS, Galileo, BeiDou 등과 같은 다른 위성 네비게이션 시스템을 포함하여 다양한 시스템을 결합하여 위치 정확성을 향상

IMU (Inertial Measurement Unit)

IMU는 가속도계와 자이로스코프를 포함하여 차량의 가속도와 각속도를 측정하는 장치이다. IMU를 사용하여 초기 위치 추정 및 주행 중의 위치 보정에 활용할 수 있지만, 시간이 지남에 따라 오차가 누적되므로 정확한 위치 추정을 위해서는 다른 측위 기술과 결합되어 사용해야 한다.

Odometry

Odometry는 바퀴의 회전량과 이동 거리를 측정하여 차량의 상대적인 위치와 이동 경로를 추정한다. 상대적 위치 추정에 사용되므로 초기 위치 정보가 필요하며 시간이 지남에 따라 오차가 누적되므로 보통 다른 측위 기술과 결합하여 사용한다.

고정밀 지도 기반 측위 기술

cm 단위 정확도를 갖는 고정밀 지도를 사전에 구축한 뒤 활용함으로써 인지 기술의 부담을 덜어줄 수 있다. 도로 주행 환경이 바뀔 때마다 OTA(Over The Air)를 통해 새로운 지도 정보를 차량에 무선 전송하여 이용할 수 있다.

사전 정의된 고정밀 지도를 기반으로 센서 정보를 맵매칭하여 측위를 수행한다. 센싱 정보에만 의존하여 위치를 파악하는 방법보다 정확한 로컬라이제이션이 가능하다. 또한 정밀 지도에 정의된 차로 정보나 교통 정보를 반영하여 주행 상황을 예측할 수 있다는 장점을 갖는다.

SLAM (Simultaneous Localization And Mapping)

SLAM은 자율주행 차량이 자신의 위치를 추정하는 동시에 주변 환경의 지도를 작성하는 기술로, 차량이 이동하면서 주변 환경을 탐색하고 이 정보를 사용하여 자신의 위치를 파악하고 주변 환경의 지도를 작성하는 것을 의미한다.

SLAM = Localization + Mapping

1. 환경 탐색 및 데이터 수집 : 차량이 이동하며 주변 환경을 탐색하면서 센서들을 통해 주변 환경의 지형, 건물, 장애물 등의 정보를 수집한다.

2. Loacalization : 수집된 센서 데이터를 기반으로 자율주행 차량이 자신의 현재 위치를 추정한다.

3. 지도 작성 : 수집된 데이터를 기반으로 주변 환경의 지도를 작성한다. 이는 주변 환경의 지형, 건물, 도로, 장애물 등의 정보를 포함한다. 이러한 지도는 이후의 위치 추정에 사용된다.

4. 지도 업데이트 : 이동하면서 새로운 데이터를 수집하면, 이를 사용하여 지도를 업데이트한다. 이를 통해 SLAM은 환경의 변화를 감지하고 지도를 최신 상태로 유지할 수 있다.

위와 같은 과정을 통해 진행되며 사용되는 센서의 종류에 따라 Visual SLAM, LIDAR SLAM 등으로 분류할 수 있다.

** 자율주행 자동차란, 운전자 또는 승객의 개입 없이 자동차 스스로 운행이 가능한 자동차로, 자동차 스스로 사람의 인지-판단-제어 기능을 대체하여 운전할 수 있는 자동차를 말한다.**

자율주행 기술 단계

미국자동차공학회 SAE에 따르면 운전자의 개입여부 및 자동화 수준에 따라 6단계로 구분된다. Level 3 이상부터 자율주행이 개입되며 테슬라, 현대 등 현재 3단계 조건부 자동화를 개발 중이다. 현재 자율주행 기술은 2단계 수준이며 인공지능을 중심으로 빠르게 발전 중이다.

우리나라를 기준으로, Level 3의 안전기준은 위와 같다. 단순히 기술적 요구사항을 충족시키는 것뿐 아니라 특정 조건에서도 탑승자 및 주변 주행자의 안전을 보장해야 하며, 비기능적 요구사항도 충족시켜야 하므로 완전 자율주행을 위해서는 풀어야 할 숙제가 많은 상태이다.

자율주행 구성

자율주행 기술은 인지-판단-제어의 단계로 나눌 수 있다.

1. 인지 : 카메라/레이더/라이다와 같은 센서들을 통해 차량이 주변 환경을 감지하고 이해하는 과정이다. 주행 환경에서 객체 인식 및 추적, 주변 상황 기반 3D 지도 생성 등의 과정이 포함되며 주변 환경을 이해하고 주행에 필요한 데이터를 확보하는 데 필수적이다.

2. 판단 : 인지 단계에서 수집한 데이터를 기반으로 수집된 정보를 분석하고 해석해 주행 경로를 설정한다. 또한 주행 중 발생할 수 있는 잠재적 위험을 평가하고 예측할 수 있다. 이를 기반으로 목적지까지 최적 경로 설정, 교통 상황에 대한 대응 등의 작업을 포함한다.

3. 제어 : 판단 단계에서 결정된 주행 명령을 기반으로 실제로 차량 제어 시스템에 적용해 움직임을 조절한다. 차량의 속도, 방향 등 제어를 조절해 목적지에 도달하거나 주변 환경에 적절히 대응할 수 있다.

또한 네트워크 측면에서 자율주행은, 차량 내외부 센서 및 교통 인프라/차량/사람 간 통신인 V2X, 차량에서 발생하는 데이터의 실시간 통신을 위한 CAN(Controller Area Network), Ethernet 통신을 비롯하여 네트워크는 차량 내외부에서 발생하는 데이터를 처리하기 위해 중요한 부분이다.

이외에 탑승자 정보제공, 운전 제어권 관리 등 사람-자동차 간 상호작용을 위한 HVI(Human Vehicle Interface) 기술들의 집약체로 자율주행 기술이 구성된다.

자율주행 이슈

자율주행 기술이 발전함에 따라 차량 내외부 네트워크 증가와 함께 보안상 위협과 시스템 오류로 인한 안전 문제가 더욱 대두되고 있다.

• 불법접근, 위장 ECU등으로 보안 위협의 경우, AUTOSAR(AUTomotive Open System Architecture, 차량 전자제어 개방형 표준 소프트웨어 구조 개발을 위한 플랫폼) 보안 규격 강화, 부팅/업데이트 시 허가된 sw인지 확인
• 차량 내부 네트워크 증가로 인한 통신 보안 위협의 경우, 차량 통신 규격인 CAN, Ethernet에 맞춰 모니터링, 사이버 공격 대응 통신 보안기술 개발
• V2X 통신 위험의 경우, 국제 표준을 준용해 통신을 위한 규격 통신보안 표준 제정, ITS 단말 신뢰 기준 제정 위와 같이 자율주행 중 발생하는 안전/보안 기술에 대해 가능한 대처를 정리해볼 수 있다.

이렇게 긴급한 주행 상황에서 자율주행 자동차의 선택이 윤리적 딜레마를 야기할 수 있는 경우, 인공지능의 운용 방식에 대해서도 사회적 합의가 필요하다. 특히 Level 3까지는 긴급상황에서 사람이 개입하지만 Level 4부터는 운전자의 개입이 불필요하기에 윤리적/사회적/경제적 여러 측면에서 인공지능의 동작에 대한 논의가 필요하다.

ISO 21448/SOTIF(Safety Of The Intended Functionality)

자동차 전기/전자 시스템의 잠재적 기능 오류로 인해 발생하는 사고를 예방하고자 ISO 26262가 발표되었다. 잠재적인 위험을 관리하고 안전성을 보장하기 위해 sw/hw 개발 검증 과정에 도입하여 자동차 제품 생명 주기에 걸쳐 안정성을 보장하기 위한 표준으로 사용된다.

SOTIF 표준은 차량의 sw/hw에 의한 오작동이 없는 경우에도 자율주행 환경에서 불합리한 위험을 방지하기 위해 등장하였다. ISO 26262를 준수하는 sw/hw이 탑재된 차량에서도 센서의 성능 제한, 예상치 못한 도로 상황의 변화, 운전자의 오용 등으로 인해 사고가 발생할 수 있다. SOTIF는 위험한 조건을 사전에 식별하기 위한 프레임워크로, 수용 가능한 수준의 위험이 있을 때까지 동작을 확인 및 검증하는 방법이다. 알려지지 않은 위험한 조건의 영역을 줄이고자 하는데 이것을 위해 충분한 시뮬레이션과 실차 테스트가 필요하다.

이러한 표준 적용을 통해 자율주행 차량 운전자의 안전을 확보할 수 있다.

스택은 후입선출(Last-In First-Out, LIFO) 의 원리를 따르는, 즉 가장 최근에 추가된 요소가 가장 먼저 제거되는 자료구조이다. 주요 메소드는 다음과 같다.

• push() : 스택의 맨 위에 원소를 추가
• pop() : 스택의 맨 위 원소를 제거하고 반환
• peek() : 스택의 맨 위 원소를 반환하지만 제거는 X (= stack[-1])
• empty() : 스택이 비어있다면 1, 그렇지 않다면 0 반환

스택은 데이터의 삽입과 삭제가 동일한 위치에서 이루어지는 자료구조로, 스택의 최상단 원소 top에 대한 접근만이 가능하다. push의 경우 top 위치에 원소가 추가되고 pop의 경우 top 위치의 원소가 제거되는 방식이다.

Overflow/Underflow

• Overflow : 스택에서 오버플로우는 스택에 push 시 스택의 공간이 가득 차서 더이상 push할 수 없을 때 발생한다. 즉 스택이 할당된 메모리 공간을 초과해 저장하려고 할 때 발생하는데 주로 재귀호출이 중첩되거나 반복문에서 스택에 많은 데이터를 삽입할 때 발생할 수 있다.
• Underflow : 스택에서 pop 연산 시 스택이 비어있어 제거할 데이터가 없는 상황일 때 발생한다.

위처럼 스택에서 오버/언더플로우를 방지하기 위해 연산 전 적절한 검사 수행 이후에 연산을 수행하도록 하여야 한다.

스택 구현

파이썬에서 리스트를 통해 간단히 스택을 구현할 수 있다.

class Stack:
    def __init__(self):
        self.stack = []

    def empty(self):
        return len(self.stack) == 0

    def push(self, element):
        self.stack.append(element)

    def pop(self):
        if not self.empty():
            return self.stack.pop()
        else:
            raise IndexError("cannot pop because of an empty stack")

    def peek(self):
        if not self.empty():
            return self.stack[-1]
        else:
            raise IndexError("cannot peek because of an empty stack")

    def size(self):
        return len(self.stack)

내장 라이브러리 사용 - Deque

from collections import deque

stack = deque()
stack.append(1)    # 원소 삽입
stack.pop()        # 
stack[-1]    # (=peek)

파이썬에서는 스택을 위한 별도 라이브러리는 존재하지 않아 양쪽 끝으로의 추가와 제거를 지원하는 collections 모듈의 deque(Double-Ended Queue)를 이용해 사용할 수 있다.

스택의 top 부분에 대해서만 push, pop, peek 연산이 수행되므로 모두 O(1)의 시간 복잡도를 갖는다. 비교적 간단한 구조를 갖고 있어 효율적으로 연산이 수행될 수 있다.

Queue (큐)

큐는 스택과 달리 선입선출(First-In First-Out, FIFO) 의 원리를 따르는 자료구조로, 가장 먼저 삽입된 데이터가 가장 먼저 제거된다. 큐에서는 다음의 주요 연산을 지원한다.

• enqueue() : 큐의 가장 뒤쪽에 원소 삽입
• dequeue() : 큐의 가장 앞쪽 원소를 제거하고 반환
• peek(), front() : 큐의 맨 앞 원소를 조회, 제거하지는 않고 조회만
• isEmpty() : 큐가 비어있는지 반환
• size() : 큐 사이즈 반환

Overflow/Underflow

특히 배열을 이용한 큐 경우, 스택과 마찬가지로 오버플로우와 언더플로우 발생에 유의해야 한다.

• Overflow : 큐에 데이터를 삽입(enqueue) 시 큐의 저장 용량을 초과한 데이터를 추가하려고 할 때 발생, 따라서 enqueue 전에 확인해야 함
• Underflow : dequeue 시 큐에 데이터가 없는 상황에서 dequeue를 시도할 때 발생, 큐가 비어있는지 확인하고 dequeue 수행

큐 구현

큐 또한 스택과 마찬가지로 리스트를 사용해 구현이 가능하다.

class Queue:
    def __init__(self):
        self.queue = []

    def enqueue(self, item):
        self.queue.append(item)

    def dequeue(self):
        if not self.is_empty():
            return self.queue.pop(0)
        else:
            raise IndexError("cannot dequeue because of an empty queue")

    def peek(self):
        if not self.is_empty():
            return self.queue[0]
        else:
            raise IndexError("cannot peek because of an empty queue")

    def is_empty(self):
        return len(self.queue) == 0

    def size(self):
        return len(self.queue)

내장 라이브러리 사용 - Queue

from queue import Queue

queue = Queue()
queue.put(1)
queue.put(2)
queue.put(3)

queue.get()        # (=dequeue)
queue.queue[0]    # (=peek)
queue.empty()
queue.qsize()

파이썬 collections 모듈의 Queue 라이브러리를 사용함으로써 큐를 간단히 사용할 수 있다. 이 때 enqueue put, dequeue는 get, peek은 queue[0]로 사용할 수 있다.

큐에서 데이터의 삽입과 제거는 각각 정해진 큐의 맨 뒤와 앞에서만 이루어지가 때문에 모두 O(1)의 시간 복잡도를 갖는다. peek, size 연산 또한 마찬가지이다.

스택 vs 큐

그래프 탐색이란 정점 vertex와 간선 edge로 이루어진 그래프 네트워크에서 특정한 목적을 갖고 정점을 방문하는 것을 말한다. 다음은 주요한 그래프 탐색 알고리즘이다.

BFS (Breadth-First Search)

너비 우선탐색 BFS는 그래프에서 가까운 정점부터 먼 정점까지 차례로 탐색하는 알고리즘이다.

큐(Queue)를 이용해 구현할 수 있으며 동작과정은 다음과 같다.

1. 시작 정점(3)을 방문하고, 해당 정점을 큐에 넣는다.
2. 큐가 빌 때까지 다음을 반복:
   • 큐에서 정점(3)을 꺼내 해당 정점과 연결된 모든 정점(5, 8, 25)을 큐에 넣고 방문한다.
   • 큐에서 방문하지 않은 정점(5)을 꺼내 해당 정점과 연결된 모든 정점(1,2)을 큐에 넣고 방문한다.
   • 큐에서 방문하지 않은 정점(8)을 꺼내 해당 정점과 연결된 모든 정점(none)을 큐에 넣고 방문한다.

BFS에서 큐를 사용하는 이유는 BFS의 특성 때문으로, 시작 정점으로부터 인접한 정점들을 순차적으로 탐색하기 때문에 선입선출(FIFO) 구조의 큐를 사용함으로써 먼저 들어온 정점부터 처리할 수 있다. 또한 방문할 정점을 큐에 넣기 전에 방문 여부를 체크해 중복 방문을 방지할 수 있다.

구현 코드

from collections import deque

def bfs(graph, start):
    visited = []    # 방문여부 저장
    queue = deque([start])        # 큐에 시작노드 추가

    while queue:
        node = queue.popleft()
        if node not in visited:        # 큐에서 꺼낸 노드가 방문하지 않은 노드라면
            visited.append(node)    # 방문리스트에 추가하고
            queue += graph[node]    # 해당 노드와 연결된 노드를 큐에 추가

    return visited

너비 우선 탐색 BFS의 시간 복잡도는 O(V+E) 로, 각 정점을 최대 한 번씩 방문하고 간선도 최대 한 번씩 검사하기 때문이다. 가까운 정점부터 먼 정점까지 차례로 탐색하므로 최단 경로를 찾는 데 유용한 알고리즘이다.

DFS (Depth-First Search)

깊이 우선탐색 DFS는 그래프나 트리 구조에서 시작 노드에서부터 시작하여 가능한 한 깊이 있는 경로를 탐색하고, 더 이상 진행할 수 없는 상황에 도달하면 역추적하여 다른 경로를 탐색하는 알고리즘이다.

일반적으로 1. 스택(Stack)이나 2. 재귀함수를 통해 구현할 수 있으며 동작과정은 다음과 같다.

1. 스택(Stack)

DFS에서는 한 정점에서 시작해 해당 분기를 완전히 탐색하기 때문에 후입선출(LIFO) 구조의 스택을 통해 깊이 우선탐색을 구현할 수 있다. 과정은 다음과 같다.

1. 시작 노드를 스택에 넣는다.
2. 스택이 빌 때까지 다음을 반복:
   • 스택에서 노드를 하나 pop
   • 해당 노드를 방문하지 않았다면 방문한다.
   • 해당 노드의 인접 노드 중 방문하지 않은 노드를 스택에 넣는다.

구현코드

def dfs(graph, start):
    visited = set()  # 방문여부 저장
    stack = [start]  # 스택에 시작노드 추가
    result = []  # 방문한 노드를 저장할 리스트

    while stack:
        node = stack.pop()
        if node not in visited:  # 스택에서 꺼낸 노드가 방문하지 않은 노드라면
            visited.add(node)  # 방문리스트에 추가
            result.append(node)     # 결과리스트에 추가

            for neighbor in graph[node]:    # 해당 노드의 인접 노드 중 방문하지 않은 노드 스택에 추가
                if neighbor not in visited:
                    stack.append(neighbor)

    return visited

2. 재귀함수

1. 시작 노드를 방문하고 방문 여부를 표시
2. 모든 인접 노드에 대해 방문할 때까지 다음을 수행: 방문하지 않은 인접 노드가 있다면 해당 노드에 대해 재귀 호출

구현 코드

def dfs_recursive(graph, node, visited, result):
    if node not in visited:  # 현재 노드를 방문하지 않았다면
        visited.add(node)  # 방문 표시
        result.append(node)    # 결과 추가

        for neighbor in graph[node]:  # 현재 노드와 연결된 모든 인접 노드에 대해
            dfs_recursive(graph, neighbor, visited, result)  # 재귀 호출
    return result

깊이 우선탐색 DFS도 BFS와 바찬가지로 모든 정점을 한 번씩 방문하고, 각 간선도 최대 한 번씩 검사하기 때문에 시간 복잡도는 O(V+E) 이다. : 인접 리스트 인접 행렬 로 표현된 경우 각 정점에서 다른 정점으로의 연결 관계를 확인할 때 상수 시간 O(1)의 시간이 소요되어 모두 확인할 경우 O(V)만큼 소요되므로, O(V^2) 의 시간 복잡도를 갖는다.

BFS vs DFS

일반적으로 탐색은

• 주어진 데이터에서 특정 값을 찾고자 할 때
• 정렬되지 않은 데이터에서 max/min 값을 찾고자 할 때
• 그래프나 트리 구조에서 경로를 찾아야 할 때
• 데이터베이스에서 특정 레코드를 검색할 때

위와 같은 상황처럼 주어진 자료구조에서 원하는 항목을 찾기 위해 사용된다. 탐색하려는 대상 자료구조에 따라 다음과 같이 나눌 수 있다.

선형 탐색 (Linear Search)

• 가장 간단하면서 기본적인 탐색 알고리즘으로
• 리스트나 배열과 같은 자료구조에서 원하는 항목을 순차적으로 검색하는 방법
• 데이터를 처음부터 끝까지 한 칸씩 움직이면서 찾는 값과 하나하나 비교하며 동작

시간 복잡도는 O(n)으로, 리스트나 배열의 길이에 비례해 탐색 시간이 증가한다. 가장 간단한 방법으로 데이터가 정렬되어 있지 않거나 크기가 작은 경우에 사용할 수 있으며 데이터의 크기가 크거나 효율성이 중요한 경우에는 성능이 떨어진다.

이진 탐색 (Binary Search)

• 정렬된 배열을 가정하고, 정렬된 배열에서 중간 값과 비교하여 좌우로 좁혀가며 탐색
• 배열의 중간 값과 비교해 작으면 왼쪽 부분을, 중간 값보다 크면 오른쪽 부분을 대상으로 다시 탐색

구현 코드

def binarySearch(search_list, search, left=0, right=None):
    # 각각 왼쪽, 오른쪽 끝 인덱스를 나타내는 left, right
    if right is None:    # right 초기 설정
        right = len(search_list) - 1

    while left <= right:
        now = (left + right) // 2    # 중간 인덱스 now

        if search_list[now] < search:    # now 기준 오른쪽 부분 탐색
            left = now + 1
        elif search_list[now] > search:        # now 기준 왼쪽 부분 탐색
            right = now - 1
        else:
            return now

    return -1    # 찾으려는 값이 리스트에 없으면 -1 리턴

이진 탐색의 시간 복잡도는 O(log n)으로 탐색하고자 하는 데이터가 정렬되어 있고 대용량 데이터의 경우 효율적인 탐색 알고리즘이다. 하지만 정렬된 데이터에 새로운 데이터의 삽입/삭제가 필요한 경우 O(n)의 시간 복잡도를 갖기 때문에 데이터의 삽입/삭제가 빈번한 경우에는 경우 불리하다.

Introduction

해당 논문에서는 차량용 내비게이션에서 사용되는 경로탐색 알고리즘에 대해 다루고 있다. 차량용 내비게이션은 GPS를 활용해 차량의 위치를 파악하고 경로를 탐색하는데 사용된다. 연구 당시 내비게이션에서는 운전자용 Database에 180만개의 링크를 이용해 경로를 탐색하였다. 하지만 이런 식으로 링크 간 경로를 탐색함에 있어 시작지점에서 목적지점까지 거리가 멀어질수록 연산비용은 급격히 증가하게 된다.

경로탐색 알고리즘에 있어 기본적인 알고리즘인 다익스트라 알고리즘은 항상 최단 경로를 찾을 수 있지만 탐색가능한 모든 경로를 검색하기 때문에 연산량이 많은 알고리즘이다.

A⁕ 알고리즘에서 탐색시간은 탐색할 노드를 저장하는 open list 크기에 따라 비례하는데 시작지점과 목적지점 간 거리가 멀수록 open list의 크기가 증가하여 연산량이 증가하게 된다. 따라서 open list의 크기를 줄이는 것이 관건이지만 잘못된 휴리스틱을 적용한다면 탐색 효율이 저하되는 결과를 가져오기도 한다. 또한 A⁕ 알고리즘은 휴리스틱에 근거해 탐색공간을 줄일 수 있지만 최단 경로를 보장하지는 못한다는 한계점을 갖는다.

Related work

경로탐색 과정에서 시작지점과 목적지점 간 거리가 멀어질수록 연산량에 따라 늘어나는 탐색 시간을 단축시키기 위해 다음과 같은 연구들이 진행되었다.

1) Bi-directional search

Bi-directional 검색 방식은 경로탐색 과정에서 시작지점과 목적지점을 동시에 탐색하는 방식이다. 일반적인 경로탐색 알고리즘에서 단방향 탐색은 시작지점에서 목적지점까지 한 방향으로 탐색만 진행한다. 반면 양방향 탐색 방식은 두 개의 탐색 그래프를 사용한다.

시작지점에서 목적지점으로 이동하는 Forward Search와 목적지점에서 시작지점으로 이동하는 Backward Search 두 개의 탐색 그래프를 통해 동시에 탐색하면서 시작지점과 목적지점 중간에서 만나는 지점을 찾게 된다.

이런 식으로 단방향 탐색에 비해 탐색 과정에서 필요한 연산량을 줄여주며 탐색 거리가 멀어질수록 탐색 시간을 줄여줄 수 있다.

2) LRTA⁕

LRTA⁕(Learning Real Time A⁕) 알고리즘은 실시간 경로탐색 문제에 사용되는 학습 기반 알고리즘이다. A⁕ 알고리즘을 기반으로 실시간으로 환경을 학습하며 탐색 과정을 지속적으로 최적화하므로 긴 거리의 경로 탐색에 있어 효율성을 개선한다.

LRTA⁕는 탐색을 진행하며 환경에 대한 정보를 학습하는데 이 때 탐색 경로를 결정할 때 현재까지 학습된 정보를 사용해 더 효율적인 결정을 내릴 수 있도록 한다. 탐색 과정 중 휴리스틱 값을 실시간으로 업데이트하며 초기에 부정확할 수 있는 휴리스틱 추정치를 점차 개선함으로써 점진적 학습 과정을 통해 탐색 시간을 절약할 수 있다.

탐색 중에 얻은 새로운 정보를 기반으로 탐색 경로를 동적으로 조정하는데, LRTA⁕의 성공적인 적용은 적절한 휴리스틱 함수의 선택과 초기 설정에 크게 의존하므로 이를 고려해 신중한 휴리스틱 함수 설계가 필요하다.

3) IDA⁕

IDA⁕ 알고리즘은 A⁕ 알고리즘의 변형으로 시작지점과 목적지점 간의 예상 비용을 휴리스틱 함수를 통해 계산하고 총 비용을 최소화하는 경로를 탐색한다는 점에서 동일하지만, IDA⁕ 알고리즘은 모든 노드를 메모리에 저장하지 않고 현재 경로의 비용과 예상 비용의 합이 특정 임계값을 초과할 경우에는 해당 경로를 버리고 다른 경로를 탐색하여 탐색 시간을 줄일 수 있다.

최적 경로를 찾을 때까지 반복적으로 경로를 탐색하며 현재 경로 비용과 예상 경로 비용이 임계값인 '바운드'를 초과하지 않도록 탐색한다. 이 바운드 값은 각 반복마다 업데이트된다.

IDA⁕ 알고리즘은 DFS를 기반으로 휴리스틱 함수를 사용하며 최적 경로를 탐색한다.

하이브리드 경로탐색 알고리즘

논문에서는 최단 거리 경로탐색 알고리즘인 다익스트라 알고리즘과 A⁕ 알고리즘을 결합한 탐색 알고리즘을 제시한다. 두 알고리즘을 결합하여 사용하기 위해 논문에서는 Level이라는 새로운 파라미터를 정의한다. Level은 검색 시작지점으로부터 얼마나 떨어진 노드인지를 나타낸다 (시작지점 노드에 가장 이웃한 노드는 Level-1(이하 L1), 다음은 L2 ...)

해당 level에 따라 알고리즘의 적합도 f(n)을 위와 같이 나타낸다. 최대 Level을 만족하기 전까지는 다익스트라 알고리즘을 이용해 최단거리 경로를 탐색하다가 최대 level이 되는 경우에만 A⁕ 알고리즘으로 전환하는 방식으로 진행된다. 위 적합도 식에서 임계값이 되는 Level 값은 사용자 설정에 따라 변경 가능하다.

즉, level 값이 증가할수록 다익스트라 알고리즘에서 open list의 크기가 증가할 때 A⁕ 알고리즘을 적용해 이를 억제시킨다는 것이다. 이 때 다익스트라 알고리즘의 open list는 A⁕ 알고리즘의 open list와는 서로 다른 리스트이다. 알고리즘 동작에 대해 자세히 살펴보자.

동작 과정

[초기화 과정]

1. 다익스트라와 A⁕ 알고리즘을 위한 각각의 open list D0, A0을 생성한다. 두 알고리즘 공용의 close list CLOSE도 생성한다. D0는 A0보다 level 값을 더 저장할 수 있다.
2. 시작지점 노드를 P라고 할 때, P를 D0에 추가한다. (초기 D0에는 P만 존재하며 level=0인 상태)

[다익스트라 탐색 과정]

1. P 노드에 이웃한 노드 n을 찾아 n이 D0 or CLOSE에 존재하지 않을 경우 D0에 n을 추가하고 n.level += 1로 갱신한다.
2. D0에서 최소 평가도 값을 갖는 노드 m을 CLOSE에 추가한다.
3. m이 목적지점 노드라면 성공종료, D0가 empty list라면 실패종료한다.
4. m.level이 설정된 임계 Level보다 작으면 [다익스트라 탐색 과정]으로, 크다면 다음 [A* 탐색 과정]으로

[A⁕ 탐색 과정]

1. A0를 (A0 Union D0) 으로 통합한 뒤 A0의 모든 평가도를 다음과 같이 갱신한다.
2. A0에서 최소 평가도 값을 갖는 노드 K라고 할 때, K.level = 0으로 설정, K를 CLOSE에 추가한다.
3. D0을 empty list로 초기화하고 [다익스트라 탐색 과정]으로

다익스트라 알고리즘과 A⁕ 알고리즘 각각 시작 노드로부터 최단 경로를 탐색하기 위해 자체적인 open list를 유지하며, 최소 평가도를 갖는 노드를 선택해 공용의 close list에 추가하며 탐색을 진행한다. 마지막 과정에서 A0 리스트와 D0 리스트를 합쳐 평가도를 갱신함으로써 다음 노드를 효율적으로 선택할 수 있게 된다.

Results

논문에서 제시한 하이브리드 알고리즘의 최단경로 탐색에 대해 1. 인공지도와 2. 실제 지도 데이터를 기반으로 컴퓨터 시뮬레이션한 결과를 통해 level값에 따른 연산비용과 측정 결과를 나타내었다.

1. 인공지도

인공지도를 이용한 시뮬레이션은 40 by 40로 최대 1600개의 노드를 표기할 수 있는 지도를 기반으로 한다. 각 노드 간 거리는 모두 1로 가정한다. Level에 따른 적합도 결과를 비교하기 위해 L1, L4, L10으로 나누어 비교하며 노드 S에서 시작해 노드 E에 도달하는 것을 목적으로 한다. 이 때 최단거리 경로는 분홍색 경로, 경로탐색을 위해 방문한 경로는 검은색 경로로 표시하였다. L1에서는 다익스트라 알고리즘을 적용하지 않고 A⁕ 알고리즘만으로 경로 탐색을 수행하였다. 따라서 탐색 공간은 기존 A⁕ 알고리즘과 동일한 결과를 보인다.

L4의 경로탐색 결과와 탐색공간을 보면 S에서 3번째 이웃노드까지만 다익스트라 알고리즘으로 탐색한 후 A⁕ 알고리즘으로 전환하였다. 이후 A⁕ 알고리즘에서 노드들의 적합도를 평가하여 다시 다익스트라 알고리즘으로 경로를 탐색한 것을 확인할 수 있다.

L10의 경우 S에서 9번째 이웃 노드가 찾아질 때까지 다익스트라 알고리즘을 적용한 뒤 A⁕로 전환되었다.

결과를 종합해보면 Level 값에 따라 탐색공간의 차이가 있었다. L1보다 L10의 경우 더 많은 경로를 탐색하였으며 이에 따라 최단 경로를 찾을 수 있는 가능성이 높아진다고 볼 수 있다.

위는 L1, L4, L10 탐색별 open list에서 경로 길이에 따른 최적 적합도에 해당하는 노드를 선정하기 위해 수행한 비교 횟수를 나타낸다. 탐색 경로길이가 길어질수록 L10보다 L1에서 더많은 비용을 확인할 수 있다. 경로길이>20 부분에서 경로길이가 증가함에 따라 연산비용은 큰 폭으로 차이가 나게 된다.

Level 값에 따른 누적 연산비용 비교 그래프이다. 연산비용 관점에서 차이가 크기 때문에 경로탐색하려는 시작지점과 목적지점 간에 따른 적합한 level을 설정하는 것이 중요하다.

2. 실제 지도

ITS의 전자도로망 지도 데이터를 이용해 실제 지도를 기반한 시뮬레이션을 진행한 결과로, level을 L16, L32, L64로 나누어 실험하였다. 또한 알고리즘 간 차이를 비교하기 위해 다익스트라, A⁕, LRTA⁕, 하이브리드 알고리즘을 함께 비교하였다. 서울 지도를 기반으로 장거리, 중거리, 단거리 경로탐색에 있어 다익스트라, A⁕, LRTA⁕ 알고리즘을 적용한 경로 결과이다. 분홍색 경로가 다익스트라, 파란색은 A⁕, 초록색은 LRTA⁕, 빨간색은 제안하는 하이브리드 알고리즘이다.

알고리즘별 탐색경로에 대한 경로거리와 연산비용을 비교한 결과는 다음과 같다. path1, path2 경우 LRTA⁕의 경로거리가 다른 알고리즘보다 다소 길지만 path3의 경우 모든 알고리즘의 경로거리가 비슷하였다. 하지만 경로탐색에 수행된 연산비용은 path1, path2, path3 모든 경우에 대해 제안된 하이브리드 알고리즘이 다른 알고리즘에 비교해 낮음을 확인할 수 있었다.

각 실제도시 맵에 대한 경로거리 및 연산비용을 고려해 선정된 최적의 level을 정리한 표로, 실험 결과 하이브리드 알고리즘의 성능이 Level 값에 민감함을 보였다. 따라서 주어진 도로환경의 최적의 Level 값을 선정하는 것이 관건이기 때문에 별도 학습과 같은 과정을 통해 최적 Level을 찾아내는 것이 중요하다.

Conclusion

최단경로 탐색을 위해 다양한 환경에서 작동하는 많은 알고리즘이 존재한다. 하지만 탐색하려는 거리가 긴 경우, 경로탐색을 위한 비교연산의 횟수가 급격히 증가한다는 문제가 생긴다. 이를 해결하기 위해 완전탐색 알고리즘인 다익스트라 알고리즘을 기본 탐색방식으로 채택하며, 선택적 알고리즘인 A⁕ 알고리즘의 기법을 활용하는 하이브리드 알고리즘을 제안하였다.

다익스트라 알고리즘과 A⁕ 알고리즘이 각각 별도의 open list를 사용하며 open list의 급격한 증가를 방지하여 연산비용을 줄일 수 있다. 또한 다익스트라 알고리즘으로 최단 경로를 탐색하기 때문에 A⁕ 알고리즘만으로 찾을 수 없었던 경로도 고려할 수 있도록 하였다.

본 하이브리드 알고리즘을 검증하기 위해 인공지도와 실제지도를 통해 각 알고리즘별 경로거리와 연산비용을 비교분석하였고 그 결과 연산비용에 있어 이점을 갖는다는 것을 확인하였다. 하지만 하이브리드 알고리즘은 Level이 증가할수록 다익스트라 알고리즘에 근접하고, 작아질수록 A⁕ 알고리즘에 근접하게 되는 특징을 갖기 때문에 목적으로 하는 경로탐색의 지역 특성에 따른 최적의 Level을 결정할 수 있는 추가적인 학습 및 알고리즘 연구가 필요하다.

A* 알고리즘은 그래프에서 시작 노드에서 목표 노드까지의 최단 경로를 효율적으로 찾기 위해 1968년 Peter Hart, Nils Nilsson, Bertram Raphael에 의해 처음 제안되었다. A-star 알고리즘의 핵심은 적절한 휴리스틱을 통해 최적의 경로를 가장 빠르게 찾아내는 것으로, 이를 위해 실제 비용(g(n))과 휴리스틱 비용(h(n)) 두 가지 주요 요소를 활용한다.

f(n) : 출발 노드에서 목표 노드까지 최적 경로를 탐색하기 위한 평가함수로, g(n) + h(n) g(n) : 실제 비용으로, 시작 노드로부터 현재 노드까지의 비용 h(n) : 휴리스틱 비용으로, 현재 노드에서 목표 노드까지의 예상 비용

또한 다음의 요소들을 추가적으로 갖는다.

열린 목록 (Open List) :

• 아직 방문하지 않았지만, 앞으로 방문할 가능성이 있는 노드들의 집합 (아직 해당 노드를 통해 이웃 노드로의 이동 가능성을 모두 탐색하지 않은 상태)

• Open list는 각 노드의 F값(F = G + H)에 따라 정렬되고 F값이 가장 낮은 노드가 가장 유망한 후보로 간주되어 다음에 탐색된다.

닫힌 목록 (Closed List) :

• 이미 방문하여 이웃 노드들을 탐색한 노드들의 집합 (해당 노드와 그 노드의 이웃들에 대한 탐색이 완료된 상태)

• Closed list에 한 번 추가된 노드는 더 이상 탐색 과정에서 고려되지 않는다. 이를 통해 알고리즘의 효율성을 높이고, 같은 노드를 반복해서 탐색하는 것을 방지할 수 있다.

A* 알고리즘 과정

1. 초기화 : 시작 노드를 열린 목록에 추가 (시작 노드의 g(n)=0)
2. 노드 선택 : 열린 목록에서 f(n) 값이 가장 낮은 노드를 현재 노드로 선택
3. 목표 확인 : 현재 노드가 목표 노드인지 확인 (목표 노드라면 경로를 추적하여 반환)
4. 이웃 탐색 : 현재 노드의 이웃들을 검사하며, 각각에 대해 g(n), h(n), f(n)을 계산. 이웃이 열린 목록에 이미 있다면, 더 낮은 g(n)값으로 업데이트할지 결정합니다.
5. 반복 or 종료: 열린 목록이 비어있으면 경로를 찾을 수 없는 것으로 판단합니다. 그렇지 않다면, 2번 단계로 돌아가 과정을 반복

위 과정을 통해, 알고리즘은 최적의 경로를 점진적으로 좁혀나가며 최종적으로 목표 노드까지의 최단 경로를 찾아낼 수 있다.

특징

• 주어진 휴리스틱 함수가 일관성 또는 접근성 조건을 만족한다면, 목표에 도달하는 최적의 경로를 보장한다
• 탐색 공간 내 경로가 존재한다면 A* 알고리즘은 반드시 경로를 찾을 수 있다
• A* 알고리즘 성능은 휴리스틱 함수의 선택에 크게 의존한다 (선정한 휴리스틱 함수가 현재 노드에서 목표 노드까지의 실제 비용을 정확하게 예측할수록 최적 경로를 위해 필요한 최소한의 노드만을 검사할 수 있어 적절한 휴리스틱 함수 선택이 중요)
• A* 알고리즘은 탐색 과정에서 더 낮은 F값을 가진 노드를 발견하면 해당 노드로 탐색경로를 변경하여 동적 탐색이 가능하다

구현 코드

import heapq

class Node:
    def __init__(self, state, parent=None, g=0, h=0):
        self.state = state
        self.parent = parent
        self.g = g  # G value
        self.h = h  # H value

    def f(self):
        return self.g + self.h

    def __lt__(self, other):
        return self.f() < other.f()

def astar(start_state, goal_state, heuristic, neighbors):
    start_node = Node(start_state, g=0, h=heuristic(start_state, goal_state))
    open_list = []
    closed_set = set()

    heapq.heappush(open_list, start_node)

    while open_list:
        current_node = heapq.heappop(open_list)

        if current_node.state == goal_state:
            path = []
            while current_node:
                path.append(current_node.state)
                current_node = current_node.parent
            return path[::-1]

        closed_set.add(current_node.state)

        for neighbor_state in neighbors(current_node.state):
            if neighbor_state in closed_set:
                continue

            g = current_node.g + 1
            h = heuristic(neighbor_state, goal_state)
            neighbor_node = Node(neighbor_state, parent=current_node, g=g, h=h)

            if neighbor_node not in open_list:
                heapq.heappush(open_list, neighbor_node)
            elif g < neighbor_node.g:
                neighbor_node.g = g
                neighbor_node.parent = current_node

    return None

def manhattan_distance(state, goal_state):
    x1, y1 = state
    x2, y2 = goal_state
    return abs(x1 - x2) + abs(y1 - y2)

def get_neighbors(state):
    x, y = state
    neighbors = [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
    return [(nx, ny) for nx, ny in neighbors if 0 <= nx < 5 and 0 <= ny < 5]

if __name__=="__main__":
    start = (0, 0)
    goal = (4, 4)
    path = astar(start, goal, manhattan_distance, get_neighbors)
    print(path)

A* 알고리즘 과정에 대해 구현한 코드로, (5,5) 격자 내에서 (0,0)에서 출발해 (4,4)으로 도달하는 것을 목적으로 하며 각 점에서는 상하좌우로만 이동가능하다. 각 이동의 비용은 1로 고정하였고 휴리스틱 함수로는 맨해튼 거리를 이용하였다.

A* vs 다익스트라 알고리즘

A* 알고리즘과 다익스트라 알고리즘은 모두 그래프 탐색 알고리즘이지만 목적과 동작 방식에 있어서 차이가 있다.

1. (One-to-One) : 한 출발점에서 한 도착점까지의 최단 경로 찾기
2. (Many-to-One / One-to-Many) : 여러 출발점에서 하나의 도착점/까지 최단 경로, 각 출발지/에서 도착점까지 최단 경로를 찾은 뒤 그 중에서 최단 경로 선택
3. (Many-o-Many) : 여러 출발점에서 여러 도착점까지의 최단 경로

Dijkstra algorithm

단일 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 그래프 탐색 알고리즘(One-to-Many)으로, 네트워크가 가중 그래프로 표현된다. 이 때 음수 가중치는 존재하지 않으며 도로 네트워크, 통신 네트워크 등에서 주로 활용된다.

동작 과정

# 전체적 동작 과정에 대한 pseudo code

다익스트라(그래프 G, 시작 노드 s):
    # 거리 테이블 초기화 : 출발 노드까지의 거리를 무한대로 설정하고, 시작 노드의 거리는 0으로 설정
    거리테이블 = {노드: 무한대, ...}
    거리테이블[s] = 0

    # 방문한 노드를 추적하는 집합
    방문한노드 = 빈 집합

    # 아직 처리되지 않은 모든 노드를 포함하는 우선순위 큐
    우선순위큐 = 우선순위 큐()
    우선순위큐.삽입((s, 0))  # 시작 노드

    # 우선순위 큐가 비어있을 때까지 반복
    while 우선순위큐가 비어있지 않을 때까지:
        # 현재까지 방문한 노드 중에서 거리가 가장 짧은 노드 선택
        현재노드, 현재거리 = 우선순위큐.최소거리노드_반환()
        우선순위큐.삭제(현재노드)

        # 방문한 노드에 현재 노드 추가
        방문한노드.추가(현재노드)

        # 현재 노드와 연결된 모든 이웃 노드에 대해 최단 경로 갱신
        for 이웃노드 in 현재노드의_이웃노드:
            # 출발 노드를 거쳐서 이웃 노드로 가는 거리 계산
            새거리 = 현재거리 + 현재노드에서_이웃노드까지_가는_거리

            # 현재까지의 최단 거리보다 새로운 거리가 더 짧으면 업데이트
            if 새거리 < 거리테이블[이웃노드]:
                거리테이블[이웃노드] = 새거리
                우선순위큐.삽입((이웃노드, 새거리))

    return 거리테이블

1. 시작 노드 설정 : 시작 노드를 선택하고 해당 노드로부터 갈 수 있는 모든 노드까지의 최단 경로 찾기
2. 거리 테이블 초기화 : 시작 노드를 제외한 모든 노드의 거리를 무한대 INF로 설정(시작 노드 거리는 0)
3. 우선순위 큐 : 우선순위 큐를 사용해 다음 방문할 노드를 선택(초기에는 시작 노드만 우선순위 큐에 존재)
4. 반복 수행 ① 우선순위 큐에서 거리가 가장 짧은 노드 선택(MinHeap 사용) ② 선택된 노드 방문해서 해당 노드로부터 갈 수 있는 모든 노드에 대해 현재 거리 테이블의 최단 거리보다 더 짧은 경로가 있다면 짧은 경로로 업데이트하고 우선순위 큐에 추가
5. 종료 : 위 반복을 우선순위 큐가 빌 때까지 반복하며 모든 노드에 대한 최단 경로가 결정되면 종료

코드 구현

import heapq

def dijkstra(graph, start):
    # 거리 테이블 초기화 : 시작 노드부터의 거리를 무한대로 설정
    distances = {node: float('inf') for node in graph}
    distances[start] = 0

    # 우선순위 큐 준비: (거리, 노드) 형태로 저장
    pq = [(0, start)]

    while pq:
        # 우선순위 큐에서 가장 짧은 거리의 노드 선택
        current_distance, current_node = heapq.heappop(pq)

        # 이미 처리된 노드인 경우 건너뜀
        if current_distance > distances[current_node]:
            continue

        # 현재 노드와 연결된 모든 이웃 노드에 대해 최단 거리 갱신
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

            # 현재까지의 최단 거리보다 새로운 거리가 더 짧으면 업데이트
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

if __name__=="__main__":
    # 그래프 예시 (인접 리스트로 표현)
    graph = {
        'A': {'B': 5, 'C': 3},
        'B': {'A': 5, 'C': 2, 'D': 1},
        'C': {'A': 3, 'B': 2, 'D': 4, 'E': 6},
        'D': {'B': 1, 'C': 4, 'E': 2},
        'E': {'C': 6, 'D': 2}
    }

    start_node = 'A'
    distances = dijkstra(graph, start_node)
    print("최단 거리:", distances)

그래프 정보를 딕셔너리 형태의 인접 리스트로 전달하며 딕셔너리의 키는 이웃 노드, 값은 가중치로 가정한다. heapq로 우선순위 큐를 사용하였다.

정리

다익스트라 알고리즘에서 거리 테이블은 최단 경로가 갱신될 때마다 출발 노드에서 해당 노드까지의 경로가 짧아지는 방향으로만 업데이트된다. 이러한 방식으로 더이상 업데이트되지 않을 때까지 최적의 경로를 탐색한다. 다익스트라 알고리즘은 그리디 알고리즘으로, 탐색 과정에서 한 노드에서 다른 노드로의 경로를 탐색하며 점진적으로 탐색 깊이를 증가시킨다는 점에서 BFS와 유사하다. 하지만 BFS는 unweighted 그래프에서의 탐색이라는 점에서 차이를 갖는다.

• 출발 노드로부터 다른 모든 노드 간 최단 경로를 찾기에 정확한 최단 경로를 찾을 수 있다는 장점
• 시간 복잡도는 O((V+E)logV)로, 노드와 간선의 수에 비례하여 계산 비용이 증가한다. 따라서 그래프가 매우 크거나 밀집되어 있을 경우에는 계산 시간 길어질 수도
• 그래프 구조가 동적으로 변경되는 경우, 대처 어려움

Array :

• 연속된 메모리 공간에 순서대로(연속적으로) 원소 저장
• 정적 크기 (생성될 때 크기 지정)
• 배열 중간에 원소 삽입/삭제하려면, 모든 원소 하나씩 이동
• 인덱스로 직접 접근은 List에 비해 빠른 편

List :

• 개별적 메모리에 원소 저장, 각 원소는 다음 원소를 가리키는 포인터 가짐

• 동적 크기

• 각 원소가 개별적 메모리에 저장되어 있어 삽입/삭제 용이

• 특정 위치 원소에 직접 접근 불가, 첫 번째부터 순서대로 찾아야 함

  Array는 메모리를 연속적으로 사용할 때, list는 삽입/삭제 연산이 빈번한 경우 유리

Stack vs Queue

Stack :

• Last in First Out (후입선출)
• 데이터 삽입(push), 삭제(pop)가 스택의 맨 위에서 발생
• 스택에 쌓일 수 있는 데이터 한정, stack overflow 가능

Queue :

• First in First Out (선입선출)
• 큐의 데이터 삽입은 rear에서 enqueue, 삭제는 front에서 dequeue

메모리 할당 방식에 있어 차이, 스택과 큐는 모두 선형 데이터 구조

Graph vs Tree

Graph :

• 임의 개수 노드와 간선으로 구성 (directed/undirected)
• 트리와 달리 사이클이 있을 수도 있음
• 인접 리스트/인접 행렬을 통해 저장
  
• 인접리스트 : 각 노드의 이웃 노드를 LinkedList로 저장
  인접행렬 : 노드 간 연결 여부를 이차원 행렬로 저장*

Tree :

• 계층 구조로, 각 노드는 한 개의 부모 노드와 여러 개의 자식 노드 가질 수 있음
• 부모-자식 노드 간 연결을 포인터/참조로 저장

  (종류)

• Binary Tree : 각 노드가 최대 두 개의 자식 노드를 갖는 트리 >> Binary Search Tree
• Binary Search Tree : 이진 트리의 일종, 임의 노드 기준 왼쪽 서브 트리는 모두 현재 노드 보다 작고 역도 성립. 데이터 검색/갱신 효율적
• Completely Binary Tree : 마지막 레벨을 제외한 모든 레벨의 노드가 꽉 차있는 이진 트리 >> Heap
• Heap : BST 일종, 우선순위큐 구현(MaxHeap, MinHeap), 삽입/삭제 시 힙 특성 유지 : 시간 복잡도 O(logn)

Linear Model(선형 모델)이란,

선형 모델이란 독립 변수(x)와 종속 변수(y) 간 관계가 일차식으로 표현되는 관계를 의미한다. 따라서 선형모델을 단순히 x에 대한 1차 다항식꼴만으로 제한되는 것이 아니라 x의 로그 함수나 exp 함수 등 모두 선형 모델로 표현이 가능하다.

간단히 말해서 머신러닝 공식에서 계수들이 선형결합의 관계에 있는 모델이라 할 수 있다.

선형모델에 대해 기계 학습을 하기 위해, 독립 변수와 종속 변수의 관계를 H(x) = wx + b 꼴로 놓았을 때 이 때 주어진 데이터에 가장 잘 맞는 미지수 w, b의 값을 결정하는 것이 중요한 포인트가 된다.

예제) 학습 시간에 따른 점수의 자료들을 바탕으로 학습 시간에 따른 점수를 예측해보자(Linear Model을 통해)

위의 학습 시간(x)에 따른 점수(y)의 식을 H(x) = wx + b 라고 하자. 이 때 목표는 주어진 데이터에 가장 잘 맞는 미지수 w와 b의 값을 찾는 것이다. H(x)값인 직선 식의 예상값과 원래 데이터 y값의 차이는 오류(cost/loss)라고 한다. 이를 전체 학습 데이터 m개에 대한 cost function식으로 나타내면

이 때 우리의 목표는 오류인 cost가 최소가 되는 미지수 w, b의 값을 결정하는 것이다. 다음은 w값에 따라 변화하는 cost function의 그래프를 나타낸 것이다.

Gradient Descent(경사하강법)

Gradient descent는 함수 값이 낮아지는 쪽으로 x값을 바꾸며 최종적으로 최소의 함수값을 갖도록 하는 방법이다. 원래 함수의 최소를 구하려면 미분을 이용해 미분계수가 0인 지점을 기점으로 달라지는 것을 파악하면 되지만, 경사하강법을 통해 함수의 최솟값을 찾는 주된 이유는 데이터양이 매우 큰 경우 미분 계수를 계산하는 것보다 경사하강법을 사용하는 편이 더 효율적이고 쉽게 구현할 수 있기 때문이다.

임의의 점 p에서의 접선의 기울기가

• 양(그래프가 증가하는 중)이라면 p의 왼쪽으로 이동,
• 음(그래프가 감소하는 중)이라면 p의 오른쪽으로 이동하여 최소의 함수값을 갖는 쪽으로 유도한다.

이를 위의 cost function 그래프에 대입해 살펴보자. 그래프는 H(x)의 미지수 w에 따른 cost값이다. 그래프의 파란 점에서 시작한다고 했을 때 이 때 해당 w좌표에 대한 접선의 기울기는 양이므로 왼쪽으로 계속 이동하다 최소의 함수값을 발견하게 된다.

이런 식으로 임의의 점에 대한 경사하강법을 적용한 최솟값(local minimum)을 구하였다. 하지만 구하고자 하는 것은 함수 전체에 대한 최솟값(global minimum)이다. 이렇게 그래프의 다른 쪽에 처음에 임의로 선택한 점보다 더 최소의 값을 갖는 부분도 있을 수 있기에 언제나 함수의 최솟값을 구하는 알고리즘은 아니다.

이렇게 간단한 선형 모델에서의 cost와 이를 기반으로 경사 하강법을 적용해보았다. 다음에도 선형 모델에 대해 더 알아보겠다.

이번에는 머신러닝의 학습 방법에 따른 분류인 다음의 3가지 supervised learning, unsupervised learning, reinforcement learning에 대해 알아보자.

1. Supervised Learning(지도 학습)

크게 어려울 것 없이 처음 input을 줄 때 정답을 같이 제공해 학습시키는 방법이다. 사람이 문제에 대한 답을 알고 있고, 인공지능이 그것을 알아낼 수 있도록 훈련시키고자 할 때 사용한다. 이는 다음 특징을 갖는다

• 단순하고 일반적이다
• 사람이 답을 알고 있고 인공지능이 알아내도록 훈련시킬 때 사용
• Label이 확실히 분류된 데이터를 사용한다

이러한 supervised learning도 두 가지로 나뉘는데

1-1. classification(분류)

classification technique은 입력 데이터를 특정 Label로 식별하기 위해 알고리즘에 "이산 값"을 예측하도록 요청한다.

다음의 예제를 보면 이해가 쉬울 것이다.

ex1) Naive Bayesian Classifier 과정

어떤 영화에 대한 댓글이 긍정/부정의 반응인지 분류하고 싶을 때, 긍정/부정에 대한 feature을 뽑는다. 예를 들어 최고, 재미, 짜증, 괜히 등과 같은 여러 feature를 뽑고 이를 기반으로 해 댓글들을 조사해 학습 데이터를 수집해 feature vector를 구성한다. 학습한 feature vector에서 각각 긍정, 부정이 전체 feature 중 차지하는 비율을 고려해 둘 중 큰 쪽으로 해당 feature에 대해 예측한다.

이처럼 문제에 대해 긍정인지 or 부정인지 명확하게 나뉘어지는 Label에 대해서 classification이라 한다.

ex2) Decision Tree

: 조건에 부합하도록 트리 형태로 계속 세분화해서 나누는 과정. internal nodes(feature를 나누는 질문)와 leaf node(리프 노드는 Label)로 구성된다.

ex3) k-nearest Neighbors

: 입력 데이터에 가장 가까운 k개의 데이터 레이블 중 더 많은 쪽으로 결정 만약 k=3이라면 결정할 점에 대해 가장 가까운 k(=3)개의 점 중 더 많은 쪽의 Label로 결정하는 방식이다. 이 방식은 학습 단계가 불필요하지만 k값에 따른 적용을 해야하기 때문에 예측 시간이 느리며 가장 최적의 k값을 결정하기 어렵다는 특징이 갖는다.

ex4) Linear Model

: 선형 모델로, 오류를 최소화하는 선형 모델을 찾는 방식

ex5) SVM(Support Vector Machine)

: maximum margin line을 결정하는 모델

1-2. Regression(회귀)

앞의 classification이 이산 값에 대해 예측하는 모델이었다면 regression은 continuous한 출력에 대해 예측하는 모델이다. 계속해서 변동하는 주가 예측 등이 이에 해당한다.

2. Unsupervised Learning(비지도 학습)

supervised learning가 달리 input과 함께 정답 Label이 주어지지 않고 학습시키는 방법이다. 인공지능이 주어진 input에서 패턴과 상관관계를 찾아내야 하는 머신러닝 알고리즘이다. 다음 특징을 가진다.

• 레이블이 지정되지 않은 데이터를 처리한다
• 사용자가 보다 복잡한 처리 작업을 수행할 수 있도록 한다
• 더 예측이 어렵다

ex1) k-means Clustering

: 데이터를 k개의 군집으로 묶는 알고리즘 이 때 k는 묶을 군집의 수를 의미하고 과정은 다음과 같다. k=3이라고 하자. 위의 점들 형태로 점이 분포해 있을 때 임의의 중심점 3점을 설정하고 각 데이터들을 가장 가까운 중심점의 군집으로 할당한다. 이 시행을 한 번씩 반복하고 같은 색 군집의 범위 가운데에 또다시 중심점을 재배치하고 위 과정을 반복한다. 이는 군집의 소속이 바뀌는 점이 없을 때까지 진행한다.

앞선 classification의 k-nearest 방법과 비슷한 것 같지만 완전히 다르다. classification은 미리 Label이 주어진 정보에 대해서 학습해 분류를 수행하지만 k-means clustering은 주어진 Label이 없는 상태에서 비슷한 속성을 가진 데이터들끼리 묶어준다는 차이점이 있기 때문이다.

ex2) Hierarchical Clustering

: 임의로 분포된 데이터들에 대해 가장 가까운 데이터끼리 순서대로 grouping하여 군집화(-> 작은 단위로부터 군집화를 시작해 모든 데이터를 묶을 때까지 반복하는 bottom-up 방식) or (-> 전체 데이터를 하나의 군집으로 묶고 시작하는 top-down 방식)

3.Reinforcement Learning(강화학습)

: 여러 시행착오를 통해 학습하는 방법. 이런 과정을 통해 실수와 보상을 통해 목표를 찾아가는 알고리즘이다.

• 환경에 대한 사전지식이 없는 상태로 학습 진행
• 컴퓨터가 선택한 행동에 대한 환경에 반응에 따라 보상이 주어짐
• 보상을 최대한 많이 얻는 쪽으로 행동을 유도하도록 학습 진행

이번에는 머신러닝의 학습 방법에 따른 분류에 대해 알아보았다. 다음에는 clssification 중 linear model에 대해 알아보자.

인공지능(Artificial Intelligence)이란, 인간 지능을 모방하여 작업을 수행하고 수집한 정보를 기반으로 반복적으로 개선할 수 있는 시스템 또는 기계를 의미한다.

인공지능이라 하면 딥러닝, 머신러닝 등을 가장 많이 들어보았을텐데 인공신경망을 기반해 학습하는 딥러닝은 머신 러닝의 일종이다. 이 머신 러닝 또한 앞서 말한 인간 지능을 모방해 일을 처리하는 인공지능의 한 종류이다.

머신러닝이란?

기계학습이라고도 하는 머신러닝(Machine Learning)은 경험을 통해 자동으로 개선하는 컴퓨터 알고리즘으로 볼 수 있다. 정확하게는

특정한 작업을 수행하기 위해 수많은 경험으로부터 획득한 데이터를 기반으로 모델을 자동으로 구성하여 성능을 향상시키는 컴퓨터 프로그램

이 과정은 해결해야 할 문제가 지속적으로 변화하는 등 명시적으로 문제해결이 어려울 때, 사용성이 높다. 위와 같이 머신러닝의 과정은

1. 대상에 대해 설명하는 가장 중요한 자질(feature)을 추출하고 -> feature extractor
2. feature extractor를 기반으로 학습 데이터를 수집하며 -> feature vector로 표현
3. feature vector를 통해 학습 알고리즘을 학습한다
4. 이 학습된 셋을 가지고 적용(inference/prediction)한다.

1,2,3단계의 학습 단계에서는 input -> feature extractor -> feature vector -> Machine Learning Techinque으로 발전할 때 input값과 함께 문제에 대한 정답(Label)을 제공한다. 따라서 머신러닝 테크닉에서는 이러한 학습 데이터를 기반으로 모델을 자동으로 구성할 수 있게 된다.

머신러닝에 있어서 데이터 간 label을 분류하는 자질(feature)이 중요한데 이때 어떤 feature를 사용해야 하는가에 있어서는 사람이 결정한다. 뒤에 배울 딥러닝은 이러한 사람의 개입이 필요하지 않는, 완전한 머신러닝이라고 볼 수 있다.

또한 앞서 나온 Machine Learning Technique은 supervised learning, unsupervised learning, reinforcement learning으로 나뉘어지는데 이들의 차이와 세부에 대해서는 다음에 더 알아보도록 하자.

오늘부턴 secure shell의 약자인 SSH를 이용한 putty를 이용해서 리눅스를 공부하려 한다. putty란 다른 컴퓨터에 원격으로 연결해 명령을 실행하는 프로그램이다.

putty 다운로드 링크

위를 통해 다운받고 실행시키면,

첫 화면은 이렇게 생겼고 연결하고자 하는 host ip에 접속해 실행할 수 있다. connection type으론 위의 SSH를 이용한다.

기본 명령어 및 사용법

(dir은 디렉토리, f는 파일을 의미한다)

0. ls | ls-a | ls -al list -> 디렉토리/파일 목록 보기

-a, -al : 모든 파일 출력 -l : 소유자, 권한, 크기, 날짜 등 정보 출력 -s : 파일 크기 출력 --help : 도움말 출력

** 1. mkdir | rmdir | touch | rm -f | rm -d**

mkdir (dir_name) -> to make a dir rmdir (dir_name) -> to remove a dir touch (file_name) -> to make a file rm -f -> to remove a file rm -d -> to remove a directory

2. drwxrwxrwx user, group, other의 read,write,excute에 대한 권한 여부를 나타낸다.

명령어 ls -al을 했을 때 보이는 문자열 중 맨 앞 하나는 d, l, - 중 하나가 오게 된다.

d : directory
l : link

• : file

rwx * 3 -> user, group, other respectively (r : read, w : write, x : excute)

**3. chmod**
2번의 rwx를 1비트를 이용해 권한 부여

>   r = 2^2, w = 2^1, x = 2^0; 1bit
         ex) r-w = 2^2 + 0 + 2^0 = 5
  -------------------------------
  how) chmod (755) (file_name)
          + ls -al to check out

**4. cd**
Change Directiory -> 디렉터리 이동
> cd (dir) : dir로 이동
/ : 최상위 디렉토리
. : 현재 디렉토리
.. : 상위 디렉토리
~ : 홈 디렉토리


+) 주소


>  pwd : 현지 주소 
/ : 절대 주소
   ./ : 현재 주소
   ../ : 현재 주소 상위
   ~/ : home 주소
   ----------
   ex) 
      절대 주소) cd /home/test/(dir)
       현재 주소) cd ./(dir)
       home 주소) cd ~/(dir)

**5. mv**
디렉토리나 파일을 새로운 이름이나 경로로 설정


>     mv (origin_file) (new_file or dir)
        : change the name and location of the file

** 6. cp**
파일, 디렉토리 각각을 다른 것에 복사

>     cp (origin_file) (new_file)
    cp -r (origin_dir) (new_dir)
        : copy the file or dir to another