Carla Simulator Actor 경로 설정

Client에서 사용하는 알고리즘

Carla 주행 경로 선택 과정

Client의 ego 차량은 PythonAPI.carla.agents.navigation폴더의 모듈들에 의해서 경로를 설정하고 조정하는데 그 중 global_route_planner에 경로를 설정하는 알고리즘이 들어있다.

GlobalRoutePlanner클래스를 생성할 때 _build_topology()함수를 통해 Carla Map의 Road Segment의 목록(list)을 받는다.
도로의 시작 waypoint와 끝 waypoint 객체에 대한 3D 좌표를 받고 도로에서 이동 가능한 영역의 waypoint들의 집합을 path에 저장한다.
path에 저장되는 값은 이동 가능한 waypoint들의 리스트를 나타내는 것으로 단위는 하나의 곡선 도로나 교차로와 교차로를 잇는 직선을 의미한다.(각 차선에 대해 구별-> 2차선의 경우 2개)

path에 저장된 경로들은 build_graph()함수를 통해 실제 경로 탐색에 쓰일(path_search) netwrokx 그래프를 생성한다.

이후 find_loose_ends()와 lane_change_link()함수를 실행하여 그래프 상에 막다른 길이나 차선 변경이 가능한 영역에 대해 가중치 값이 0인 특수 엣지를 추가하는 등의 작업을 수행한다.
(가중치값이란 후에 A* 알고리즘을 통해 최단 경로 계산에 쓰이는 값을 의미)

GlobalRoutePlanner클래스를 생성한 이후 path_search()함수를 반복적으로 실행하여 A* 알고리즘을 기반으로 경로 비용을 계산하여 최단 경로를 구성하는 path내에 포함된 값들의 리스트를 반환한다.

def _path_search(self, origin, destination):
    start, end = self._localize(origin), self._localize(destination)

    route = nx.astar_path(
        self._graph, source=start[0], target=end[0],
        heuristic=self._distance_heuristic, weight='length')
    route.append(end[1])
    return route

A* 알고리즘 (Client)

한점의 출발 지점에서 목표 지점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘으로 Carla에서 사용하는 path planning의 기반이다.

$f(n) = g(n) + h(n)$

• $g(n)$ : 출발 지점부터 현재 지점(n)까지에 대한 비용.
• $h(n)$ : 현재 지점(n)부터 목표 지점까지 도달하기까지 예상되는 비용.
• $f(n)$ : 총 예상 비용(출발 지점부터 목표 지점까지)

n은 현재 위치로 현재 위치까지 오기까지의 비용과 앞으로 예상되는 비용들을 계산할 때 중심 위치이다.
n은 여러 위치에서 계산되며 그 중 최종 값인 f(n)이 가장 적게 나오는 값을 최단 경로로 설정한다.

| 0 | 0 | 0 | 0 | 
| 0 | 0 | 0 | 0 | 
| 0 | 0 | 0 | 0 | 
| 0 | 0 | 0 | 0 | 

좌측 하단을 출발로 우측 상단으로 이동한다고 가정하고 한칸당 1의 비용을 가질 때
[1, 2]의 위치를 n이라고 가정하게 되면
n까지 가는 방법은 여러가지가 있게 된다.

| 0 | 7 | 8 | 9 | 
| 0 | 6 | 0 | 0 | 
| 0 | 5 | 4 | 0 | 
| 1 | 2 | 3 | 0 | 

다음의 경로로 움직이게 될 경우 n을 가기까지 걸린 비용은 5가 되고 n부터 목표 지점까지는 4의 비용을 가져 총 9의 비용을 가진다.
$f(n) = g(n) + h(n)$ 가 $9 = 5 + 4$ 형태로 이루어진 것이다.

| 6 | 7 | 8 | 9 | 
| 5 | 4 | 0 | 0 | 
| 0 | 3 | 0 | 0 | 
| 1 | 2 | 0 | 0 | 

다음의 경우는 $f(n) = g(n) + h(n)$ 가 $9 = 3 + 6$ 형태로 이루어진 것이다.

A* 알고리즘은 다음과 같은 그래프에서 최단 비용을 소모하는 경로를 찾아 최종 경로를 찾게 된다.

| 0 | 0 | 0 | 7 | 
| 0 | 4 | 5 | 6 | 
| 0 | 3 | 0 | 0 | 
| 1 | 2 | 0 | 0 | 

$f(n) = g(n) + h(n)$ -> $7 = 3 + 4$

차선 변경의 경우는 비용이 0이 되어 차선 변경이 들어가더라도 비용값에 대해 영향을 미치게 되지 않게 설정된다.

Server에서 사용하는 알고리즘

Carla Simulator는 Server내에서 Actor의 상태를 파악하고 각 Actor가 현재 위치한 waypoint의 정보에 따라 차선, 신호등, 인근 차량 등을 고려하여 경로를 계산한다.
계산하는 주기는 world.tick()마다 반복된다.

경로 추종 제어의 순서는 다음과 같다.

1. 목표 지점(waypoint)설정

차량의 현재 위치에서 가능한 경로 중 다음 waypoint 하나를 목표 지점으로 선정.

2. 차량 제어 값 계산

목표 waypoint까지 도달하기 위해 가속, 제동, 회전 등의 값을 계산.

3. 명령 수행

계산된 각 값들을 각 Actor에 전달하여 수행.

4. 최종 목적지까지 반복

각 world.tick()마다 1단계부터 3단계를 반복하여 수행.

A* 알고리즘을 사용하지 않는 이유는 Server에 돌아다니는 차량의 경우 최종 목적지가 정해지지 않고 waypoint(1m)단위로 랜덤으로 이동하기 때문이다.
따라서 매 world.tick()마다 이동 가능한 waypoint를 찾아 그 중 하나를 선택하고 이동하는 방식을 사용하기에 특정한 알고리즘을 사용하지 않는다.