격자와 로봇 반경
80분 안팎
학습 목표
0.1m 해상도 지도에서 반경 0.15m와 여유 0.05m로 장애물을 팽창합니다.
개념
빈 칸이 로봇의 통과를 뜻하지 않습니다
앞 모듈에서는 장애물 없는 바닥에서 목표점을 향해 움직였습니다. 실제 지도에 선반 한 칸을 추가하면 중심점이 빈 칸에 있어도 몸체가 선반을 스칠 수 있습니다. 따라서 탐색 전에 로봇의 크기를 지도에 반영합니다. 이 레슨은 센서로 지도를 만드는 과정이 아니라 이미 주어진 지도를 이동 가능 여부로 바꾸는 단계입니다. 완료하면 반경과 여유를 계산하고 좁은 길이 왜 닫히는지 설명할 수 있습니다.
이번 모듈은 Python 3 표준 라이브러리·gcc·bash를 사용합니다. 브라우저에는 JSON 객체 하나를 표준 입력으로 넣고 JSON 결과 하나만 출력합니다. 각 실습의 필드와 단위는 해당 prompt에 명시합니다. 로컬 zip은 독립 폴더에 풀고 bash check.sh로 실행합니다. 외부 패키지·실물 장치·ROS 2 설치는 필요하지 않습니다. 가상 시간은 제어 tick 수에 dt를 곱한 값이며 벽시계 실행 시간과 다릅니다.
지도의 기호와 행 방향을 고정합니다
grid는 같은 길이의 문자열 목록입니다. 마침표는 확인된 빈 칸, #은 점유 칸, ?는 미관측 칸입니다. 이번 정책은 ?도 장애물처럼 처리합니다. 문자열 목록의 첫 행은 지도 아래쪽이고 행 번호는 위로 증가합니다. 그림을 위에서부터 출력하려면 역순으로 보여 줍니다. 보기 편한 그림 순서를 내부 배열 순서로 착각하면 장애물과 목표의 상하 위치가 뒤집힙니다.
셀을 말할 때는 (열,행) 순서이고 배열을 읽을 때는 grid[행][열]입니다. 해상도 0.1m는 한 칸의 가로·세로 길이입니다. 21칸이면 한 변이 2.1m이며 21m가 아닙니다. 원점은 첫 칸의 중심이 아니라 영역의 왼쪽 아래 모서리입니다. 이 레슨의 팽창에는 원점이 필요 없지만 다음 좌표 변환에서 같은 정의를 유지합니다.
반경과 여유를 합칩니다
몸체는 반경 0.15m인 원으로 가정합니다. 여유 0.05m는 계획에서 추가로 확보하려는 거리입니다. 계획 반경은 두 값을 합한 0.20m입니다. 여유를 로봇 지름에 더하거나 셀 번호에 바로 더하지 않습니다. 미터인 거리와 정수인 칸 수를 분리한 뒤 k=ceil((반경+여유)/해상도)로 바꿉니다. 0.20/0.1이므로 이번 k는 2입니다.
반경이 0.151m로 바뀌면 합이 0.201m이고 k는 3이 됩니다. 반올림으로 2를 택하면 설정한 거리보다 작은 영역을 막게 됩니다. 다만 0.15+0.05 같은 실수 계산의 오차가 경계에서 불필요한 한 칸을 만들지 않도록 코드에서는 비율에서 1e-12를 뺀 뒤 올립니다. 이는 미터 단위의 큰 오차를 숨기는 장치가 아니라 알려진 부동소수점 경계 처리입니다.
이번 팽창은 정사각형으로 보수적으로 합니다
각 장애물 셀 주변에서 열 차이와 행 차이가 모두 k 이하인 셀을 막습니다. k=2이면 원래 셀을 포함해 최대 5×5칸입니다. 장애물 주변을 정확한 원으로 칠한 결과와 같지는 않습니다. 대각선 방향까지 정사각형으로 닫으므로 필요한 최소 공간보다 더 막을 수 있습니다. 이 단순 정책의 장점은 손으로 범위를 검산할 수 있고 4방향 연결을 시험하기 쉽다는 점입니다.
원본 점유 칸 전체를 닫힌 정사각 장애물로 봅니다. 그 셀에서 k+1칸 떨어진 이웃 셀 중심까지의 가장 가까운 축 거리는 (k+0.5)×해상도입니다. k×해상도보다 크므로 설정한 계획 반경 바깥입니다. 이 근거는 정해 둔 원형 몸체와 정사각 셀 모델에 관한 것입니다. 실제 선반의 돌출부나 추정 오차까지 지도에 자동으로 반영되지는 않습니다.
지도 가장자리도 이동 가능 영역을 줄입니다
장애물이 전혀 없는 지도라도 로봇의 중심이 테두리에 너무 가까우면 몸체 일부가 지도 밖으로 나갑니다. 셀 중심에서 네 경계까지 거리의 최솟값을 구해 계획 반경 이하이면 막습니다. 0.1m 해상도에서 첫 두 칸 중심은 경계에서 0.05m와 0.15m라서 닫히고 세 번째 중심의 0.25m는 열립니다. 경계 접촉은 이번 모델에서 허용하지 않습니다.
지도 밖을 빈 공간으로 간주하는 코드는 피합니다. 실습은 지도 영역 안에서만 움직인다는 계약을 갖습니다. 인덱스를 clamp해서 지도 안으로 밀어 넣는 방식은 경계 밖 목표를 다른 목표로 바꿉니다. 범위 밖은 이후 탐색 단계에서 경로 없음으로 처리해야 하고 사용자가 요청한 좌표를 조용히 수정하지 않아야 합니다.
출력과 실패를 읽습니다
원본 grid를 덮어쓰지 않고 새 문자열 목록을 만듭니다. 실행 단계의 충돌 검사는 원본 장애물을 사용하므로 두 지도를 모두 보존해야 합니다. 원본에 팽창 결과를 다시 입력하면 같은 장애물이 계속 두꺼워져 지도 전체가 닫힐 수 있습니다. 팽창이 두 번 적용된 지도는 여유를 조금 늘린 지도와 다른 결과라는 점을 테스트로 확인합니다.
빈 지도·행 길이 불일치·알 수 없는 기호는 BAD_MAP 예외이며 브라우저에서는 ERROR로 표시합니다. 해상도 0이나 음수 반경, NaN은 BAD_GEOMETRY입니다. #만 가득 나온 결과는 예외가 아니라 정상적인 차단 지도일 수 있습니다. 입력 치수, k, 가장자리 띠, 장애물 위치 순서로 확인한 뒤 실제로 통로가 충분한지 판단합니다.
제출 전에 좁은 통로를 검토합니다
팽창 함수의 TODO를 완성하고 중앙 장애물·빈 지도·미관측 셀·모서리·좁은 지도를 비교합니다. k=0이면 장애물만 남지만 지도 경계 접촉 규칙은 유지됩니다. 원본과 결과를 각각 출력해 어떤 셀이 새로 막혔는지 적습니다. 통로가 닫혔다고 반경을 줄여 테스트를 통과시키지 않습니다. 반경은 장치 치수이며 통로 폭이나 우회 경로를 먼저 검토합니다.
이번 입력은 확률을 누적하는 지도 생성기가 아닙니다. 센서로부터 점유 확률을 얻는 과정과 미관측의 의미는 더 읽기의 점유 격자 장에서 다룹니다. 프로젝트에서는 계획용 차단 지도와 실행용 원본 지도를 분리해 다음 레슨으로 넘깁니다. 안전 여유는 실험 설정으로 남기되 모든 실제 환경에 충분한 값이라고 주장하지 않습니다.
따라하기
올림 칸 수를 비교합니다
같은 해상도에서 반경이 경계값을 넘을 때의 변화를 확인합니다.
import math
for radius in (0.15,0.151):
k=math.ceil((radius+0.05)/0.1-1e-12)
print(f'radius={radius:.3f} k={k}')실행 결과
radius=0.150 k=2 radius=0.151 k=3
중앙 장애물을 팽창합니다
9×9 지도를 아래 행부터 출력합니다. 바깥 두 줄과 중앙 5×5가 닫히는 위치를 살펴봅니다.
"""Static grid planning; cells are (column,row), row 0 is the bottom."""
import math
from collections import deque
DIRECTIONS = ((1,0),(0,1),(-1,0),(0,-1))
EPS=1e-10
def validate_grid(grid):
if not isinstance(grid,list) or not grid or not isinstance(grid[0],str) or not grid[0]:
raise ValueError("BAD_MAP")
width=len(grid[0])
if any(not isinstance(row,str) or len(row)!=width or set(row)-set(".#?") for row in grid):
raise ValueError("BAD_MAP")
return width,len(grid)
def inflate(grid,resolution,radius,margin):
width,height=validate_grid(grid)
if any(type(v) not in (int,float) or not math.isfinite(v) for v in (resolution,radius,margin)) or resolution<=0 or radius<0 or margin<0:
raise ValueError("BAD_GEOMETRY")
reach=radius+margin
# Conservative square stencil; tolerance handles 0.15+0.05 roundoff.
k=math.ceil(reach/resolution-1e-12)
blocked={(c,r) for r,row in enumerate(grid) for c,v in enumerate(row) if v!='.'}
result=[]
for r in range(height):
row=[]
for c in range(width):
edge=min((c+0.5)*resolution,(width-c-0.5)*resolution,
(r+0.5)*resolution,(height-r-0.5)*resolution)
near=any(abs(c-bc)<=k and abs(r-br)<=k for bc,br in blocked)
row.append('#' if edge<=reach+EPS or near else '.')
result.append(''.join(row))
return result
g=['.'*9]*4+['....#....']+['.'*9]*4
for row in inflate(g,0.1,0.15,0.05): print(row)실행 결과
######### ######### ######### ######### ######### ######### ######### ######### #########
잘못된 입력을 구별합니다
이 예외는 통로가 닫힌 정상 결과와 다릅니다.
"""Static grid planning; cells are (column,row), row 0 is the bottom."""
import math
from collections import deque
DIRECTIONS = ((1,0),(0,1),(-1,0),(0,-1))
EPS=1e-10
def validate_grid(grid):
if not isinstance(grid,list) or not grid or not isinstance(grid[0],str) or not grid[0]:
raise ValueError("BAD_MAP")
width=len(grid[0])
if any(not isinstance(row,str) or len(row)!=width or set(row)-set(".#?") for row in grid):
raise ValueError("BAD_MAP")
return width,len(grid)
def inflate(grid,resolution,radius,margin):
width,height=validate_grid(grid)
if any(type(v) not in (int,float) or not math.isfinite(v) for v in (resolution,radius,margin)) or resolution<=0 or radius<0 or margin<0:
raise ValueError("BAD_GEOMETRY")
reach=radius+margin
# Conservative square stencil; tolerance handles 0.15+0.05 roundoff.
k=math.ceil(reach/resolution-1e-12)
blocked={(c,r) for r,row in enumerate(grid) for c,v in enumerate(row) if v!='.'}
result=[]
for r in range(height):
row=[]
for c in range(width):
edge=min((c+0.5)*resolution,(width-c-0.5)*resolution,
(r+0.5)*resolution,(height-r-0.5)*resolution)
near=any(abs(c-bc)<=k and abs(r-br)<=k for bc,br in blocked)
row.append('#' if edge<=reach+EPS or near else '.')
result.append(''.join(row))
return result
for grid,res in [(['..','.'],0.1),(['.'],0.0)]:
try: inflate(grid,res,0.15,0.05)
except ValueError as e: print(e)실행 결과
BAD_MAP BAD_GEOMETRY
확인 문제
실습
입력 객체의 grid·resolution·radius·margin을 사용해 inflate 함수를 완성합니다. 거리 단위는 m입니다. .만 빈 공간이며 #와 ?는 장애물입니다. k=ceil((radius+margin)/resolution−1e-12)인 정사각 범위를 차단하고 셀 중심의 경계 거리가 radius+margin 이하인 칸도 막습니다. 결과는 행 순서를 유지한 문자열 JSON 목록입니다. 잘못된 지도·치수는 ERROR입니다. 제공한 검증·출력 부분은 유지하고 near의 TODO만 완성합니다.
모범 답안
"""Static grid planning; cells are (column,row), row 0 is the bottom."""
import math
from collections import deque
DIRECTIONS = ((1,0),(0,1),(-1,0),(0,-1))
EPS=1e-10
def validate_grid(grid):
if not isinstance(grid,list) or not grid or not isinstance(grid[0],str) or not grid[0]:
raise ValueError("BAD_MAP")
width=len(grid[0])
if any(not isinstance(row,str) or len(row)!=width or set(row)-set(".#?") for row in grid):
raise ValueError("BAD_MAP")
return width,len(grid)
def inflate(grid,resolution,radius,margin):
width,height=validate_grid(grid)
if any(type(v) not in (int,float) or not math.isfinite(v) for v in (resolution,radius,margin)) or resolution<=0 or radius<0 or margin<0:
raise ValueError("BAD_GEOMETRY")
reach=radius+margin
# Conservative square stencil; tolerance handles 0.15+0.05 roundoff.
k=math.ceil(reach/resolution-1e-12)
blocked={(c,r) for r,row in enumerate(grid) for c,v in enumerate(row) if v!='.'}
result=[]
for r in range(height):
row=[]
for c in range(width):
edge=min((c+0.5)*resolution,(width-c-0.5)*resolution,
(r+0.5)*resolution,(height-r-0.5)*resolution)
near=any(abs(c-bc)<=k and abs(r-br)<=k for bc,br in blocked)
row.append('#' if edge<=reach+EPS or near else '.')
result.append(''.join(row))
return result
import json,sys
try:
obj=json.load(sys.stdin)
print(json.dumps(inflate(obj['grid'],obj['resolution'],obj['radius'],obj['margin'])))
except (ValueError,TypeError,KeyError,OverflowError):
print('ERROR')
더 읽기
면접 질문
- 서로 다른 좌표계의 위치를 변환하는 과정을 설명해 주시면 됩니다.