Main Content

복잡도가 다양한 환경에서의 경로 계획

이 예제에서는 PRM(확률적 로드맵) 경로 플래너를 사용하여, 주어진 맵의 두 위치 사이에 장애물 없는 경로를 계산하는 방법을 보여줍니다. PRM 경로 플래너는 주어진 맵의 자유 공간에서 임의로 샘플링된 노드들을 사용하고 서로 연결하여 로드맵을 생성합니다. 로드맵이 생성되면 맵에서 주어진 시작 위치에서 주어진 끝 위치까지의 경로를 쿼리할 수 있습니다.

이 예제에서는 가져온 데이터를 사용하여 맵을 점유 그리드 맵으로 표현합니다. 맵의 자유 공간에서 노드를 샘플링할 때 PRM은 이 이진 점유 그리드 표현을 사용하여 자유 공간을 유추합니다. 또한 PRM은 맵에서 장애물 없는 경로를 계산하는 과정에서 로봇 크기를 고려하지 않습니다. 따라서 로봇의 크기를 고려하여 실제 로봇의 충돌 회피를 보장하는 장애물 없는 경로를 계산하기 위해서는 맵을 로봇 크기에 맞춰 확장해야 합니다. PRM 경로 플래너가 장애물 없는 경로를 찾을 수 있도록 맵에서 시작 위치와 끝 위치를 정의합니다.

경로 계획을 위한 예제 맵 가져오기

load exampleMaps.mat

가져온 맵은 simpleMap, complexMap, ternaryMap입니다.

whos *Map*
  Name              Size               Bytes  Class      Attributes

  complexMap       41x52                2132  logical              
  emptyMap         26x27                 702  logical              
  simpleMap        26x27                 702  logical              
  ternaryMap      501x501            2008008  double               

가져온 simpleMap 데이터를 가지고 binaryOccupancyMap 객체를 사용하여 점유 그리드 표현을 생성합니다. 이 맵의 해상도를 미터당 셀 2개로 설정합니다.

map = binaryOccupancyMap(simpleMap,2);

binaryOccupancyMap 객체에 show 함수를 사용하여 맵을 표시합니다.

show(map)

Figure contains an axes object. The axes object with title Binary Occupancy Grid, xlabel X [meters], ylabel Y [meters] contains an object of type image.

로봇 크기를 정의하고 맵 확장하기

로봇이 어떤 장애물에도 충돌하지 않도록 하려면 맵을 PRM 경로 플래너에 제공하기 전에 로봇의 크기만큼 확장해야 합니다.

여기서 로봇의 크기는 반지름이 0.2미터인 원으로 가정할 수 있습니다. 그런 다음 inflate 함수를 사용하여 이 크기만큼 맵을 확장할 수 있습니다.

robotRadius = 0.2;

앞에서 언급했듯이 PRM은 로봇의 크기를 고려하지 않으므로 PRM에 확장된 맵을 제공해야만 로봇의 크기가 고려됩니다. inflate 함수를 사용하기 전에 맵의 복사본을 만들어 원본 맵을 보존하십시오.

mapInflated = copy(map);
inflate(mapInflated,robotRadius);

확장된 맵을 표시합니다.

show(mapInflated)

Figure contains an axes object. The axes object with title Binary Occupancy Grid, xlabel X [meters], ylabel Y [meters] contains an object of type image.

PRM을 구성하고 파라미터 설정하기

이제 경로 플래너를 정의해야 합니다. mobileRobotPRM 객체를 만들고 관련 특성을 정의합니다.

prm = mobileRobotPRM;

확장된 맵을 PRM 객체에 할당합니다.

prm.Map = mapInflated;

PRM 생성 중에 사용될 PRM 노드 개수를 정의합니다. PRM은 주어진 맵에서 주어진 노드 개수를 사용하여 로드맵을 생성합니다. 이는 입력 맵의 크기와 복잡도를 고려하여 맵에서 두 지점 사이의 해를 얻기 위해 조정해야 하는 주요 특성 중 하나입니다. 노드 개수가 많으면 조밀한 로드맵이 생성되어 경로를 찾을 확률이 커집니다. 하지만 노드 개수가 많으면 로드맵 생성 작업과 해를 찾는 작업 모두 계산 시간이 늘어납니다.

prm.NumNodes = 50;

맵에서 연결된 두 노드 사이에 허용되는 최대 거리를 정의합니다. PRM은 맵에서 이 거리만큼(또는 그 이내로) 떨어져 있는 노드들을 모두 연결합니다. 마찬가지로 입력 맵이 더 크거나 복잡하다면 이 특성도 조정이 필요합니다. 연결 거리가 크면 노드 간의 연결이 증가하여 경로를 더 쉽게 찾을 수 있지만, 로드맵을 생성하는 계산 시간이 늘어날 수 있습니다.

prm.ConnectionDistance = 5;

구성된 PRM에서 실현 가능한 경로 찾기

맵에서 경로 플래너가 사용할 시작 위치와 끝 위치를 정의합니다.

startLocation = [2 1];
endLocation = [12 10];

findpath 함수를 사용하여 시작 위치와 끝 위치 사이의 경로를 탐색합니다. 해는 시작 위치에서 끝 위치까지 이어지는 일련의 웨이포인트입니다. PRM 알고리즘의 확률적 특성 때문에 path가 다를 수 있습니다.

path = findpath(prm, startLocation, endLocation)
path = 7×2

    2.0000    1.0000
    1.9569    1.0546
    1.8369    2.3856
    3.2389    6.6106
    7.8260    8.1330
   11.4632   10.5857
   12.0000   10.0000

PRM 해를 표시합니다.

show(prm)

Figure contains an axes object. The axes object with title Probabilistic Roadmap, xlabel X [meters], ylabel Y [meters] contains 4 objects of type image, line, scatter.

크고 복잡한 맵에 PRM 사용하기

크고 복잡한 평면도를 나타내는 complexMap 데이터를 가지고 주어진 해상도(미터당 셀 1개)를 사용하여 이진 점유 그리드 표현을 생성합니다.

map = binaryOccupancyMap(complexMap,1);

맵을 표시합니다.

show(map)

Figure contains an axes object. The axes object with title Binary Occupancy Grid, xlabel X [meters], ylabel Y [meters] contains an object of type image.

로봇 크기를 기반으로 맵 확장하기

장애물 회피를 위해 로봇 크기를 고려할 수 있도록 맵을 복사하고 확장합니다.

mapInflated = copy(map);
inflate(mapInflated, robotRadius);

확장된 맵을 표시합니다.

show(mapInflated)

Figure contains an axes object. The axes object with title Binary Occupancy Grid, xlabel X [meters], ylabel Y [meters] contains an object of type image.

기존 PRM 객체를 새로운 맵과 연결하고 파라미터 설정하기

새로 확장한 맵으로 PRM 객체를 업데이트하고 기타 특성을 정의합니다.

prm.Map = mapInflated;

NumNodes 속성과 ConnectionDistance 속성을 설정합니다.

prm.NumNodes = 20;
prm.ConnectionDistance = 15;

PRM 그래프를 표시합니다.

show(prm)

Figure contains an axes object. The axes object with title Probabilistic Roadmap, xlabel X [meters], ylabel Y [meters] contains 3 objects of type image, line, scatter.

구성된 PRM에서 실현 가능한 경로 찾기

장애물이 없는 경로를 찾기 위해 맵에서 시작 위치와 끝 위치를 정의합니다.

startLocation = [3 3];
endLocation = [45 35];

시작 위치와 끝 위치 사이의 해를 구합니다. 복잡한 맵의 경우 주어진 노드 개수에 대해 실현 가능한 경로가 없을 수 있습니다(비어 있는 경로 반환).

path = findpath(prm, startLocation, endLocation);

크고 복잡한 맵에서 경로를 계획하고 있기 때문에 더 많은 개수의 노드가 필요할 수 있습니다. 하지만 노드가 몇 개나 있어야 충분할지 명확하지 않은 경우가 많습니다. 노드 개수를 조정하여 시작 위치와 끝 위치 사이에 실현 가능한 경로가 있는지 확인합니다.

while isempty(path)
    % No feasible path found yet, increase the number of nodes
    prm.NumNodes = prm.NumNodes + 10;
    
    % Use the |update| function to re-create the PRM roadmap with the changed
    % attribute
    update(prm);
    
    % Search for a feasible path with the updated PRM
    path = findpath(prm, startLocation, endLocation);
end

경로를 표시합니다.

path
path = 12×2

    3.0000    3.0000
    4.2287    4.2628
    7.7686    5.6520
    6.8570    8.2389
   19.5613    8.4030
   33.1838    8.7614
   31.3248   16.3874
   41.3317   17.5090
   48.3017   25.8527
   49.4926   36.8804
      ⋮

PRM 해를 표시합니다.

show(prm)

Figure contains an axes object. The axes object with title Probabilistic Roadmap, xlabel X [meters], ylabel Y [meters] contains 4 objects of type image, line, scatter.