KR102837566B1 - 맵 데이터를 이용한 이동 관련 연산 방법 및 그 장치 - Google Patents

Abstract

이동이 가능한 영역과 이동이 불가능한 영역이 구분되어 있는 지리적 영역에 대한 정보를 표현하는 맵 데이터를 기반으로, 이동이 가능한 영역을 통한 이동에 대한 연산을 수행함에 있어서, 그 연산 속도를 증가시키기 위한 방법 및 그 방법이 적용된 장치가 제공된다.

Description

맵 데이터를 이용한 이동 관련 연산 방법 및 그 장치{METHOD AND APPARATUS FOR MOVING-RELATED CALCULATION USING MAP DATA}

본 발명은 맵 데이터를 이용한 이동 관련 연산 방법 및 그 장치에 관한 것이다. 보다 자세하게는, 이동이 가능한 영역과 이동이 불가능한 영역이 구분되어 있는 지리적 영역에 대한 정보를 표현하는 맵 데이터를 기반으로, 이동이 가능한 영역을 통한 이동에 대한 연산을 수행함에 있어서, 그 연산 속도를 증가시키기 위한 방법 및 그 방법이 적용된 장치에 관한 것이다.

다양한 형태의 지리적 영역이 디지털 지도의 형태로 표현되고 있다. 상기 디지털 지도를 구현하는 맵 데이터를 기반으로 한 연산을 수행하는 다양한 애플리케이션들이 제공된다. 예를 들어, 내비게이션 애플리케이션은 도로를 표현하는 맵 데이터를 기반으로 하는, 가장 널리 사용되는 서비스 중 하나이다.

또 다른 예로서, 대형 창고에서의 입고 또는 출고 태스크를 자동화하기 위하여 상기 대형 창고를 표현하는 맵 데이터를 기반으로 한 연산을 수행하는 애플리케이션도 제공되고 있다. 예를 들어, 일련의 입고 및 출고 태스크를 최소 시간 내에 진행하기 위한 경로 최적화 알고리즘을 수행하는 애플리케이션이 제공된다.

한편, 상기 맵 데이터가 표현하는 지리적 영역이 커질수록, 연산량도 함께 증가하게 된다. 예를 들어, 초대형 창고의 맵 데이터는 매우 많은 셀(cell)들을 포함하여 구성될 것이고, 상기 초대형 창고 내부의 이동 가능 영역 및 상기 이동 가능 영역을 통하여 형성될 수 있는 이동 경로의 수도 매우 많을 것이다.

이처럼, 맵 데이터가 표현하는 지리적 영역의 확대에 따라, 상기 맵 데이터를 이용한 이동 관련 연산의 연산 부하가 감당하기 어려울 정도로 커지게 되면, 서비스의 제공에 있어서 많은 제한이 가해지게 된다.

한국등록특허 제1711887호 (2017.02.24 공개)

본 발명의 몇몇 실시예들을 통하여 달성하고자 하는 기술적 과제는, 맵 데이터가 표현하는 영역 내에서의 이동과 관련된 연산을 가속하는 방법 및 그 방법이 적용된 장치를 제공하는 것이다.

본 발명의 몇몇 실시예들을 통하여 달성하고자 하는 다른 기술적 과제는, 대형 창고 등 넓은 영역을 표현하는 맵 데이터를 최적화 함으로써, 컴퓨팅 리소스가 빈약한 컴퓨팅 장치에서도 상기 맵 데이터 기반의 이동 관련 연산을 수행하는데 무리가 없도록 하는 방법 및 그 방법이 적용된 장치를 제공하는 것이다.

본 발명의 몇몇 실시예들을 통하여 달성하고자 하는 또 다른 기술적 과제는, 서로 다른 스토리지 노드 간에 오프-체인 데이터를 공유함에 있어서, 공유 대상 스토리지 노드 또는 공유 대상 조직에 대한 등록 절차를 수행하는 등 사전 절차가 필요하지 않는 시스템 및 그 방법을 제공하는 것이다.

본 발명의 몇몇 실시예들을 통하여 달성하고자 하는 또 다른 기술적 과제는, 서로 다른 스토리지 노드 간의 데이터 공유 이력을 정확하게 공증하고, 그 이력을 블록체인에 기록함으로 인하여, 데이터 공유 사실의 신뢰성을 담보할 수 있는 시스템 및 그 방법을 제공하는 것이다.

본 발명의 기술적 과제들은 이상에서 언급한 기술적 과제들로 제한되지 않으며, 언급되지 않은 또 다른 기술적 과제들은 아래의 기재로부터 본 발명의 기술분야에서의 통상의 기술자에게 명확하게 이해될 수 있을 것이다.

상기 기술적 과제를 해결하기 위한, 본 발명의 일 실시예에 따른 맵 데이터를 이용한 이동 관련 연산 방법은, 동일 크기의 그리드(grid)들로 표현된 이동 가능 영역 및 이동 불가 영역을 포함하는 맵 데이터를 얻는 단계와, 상기 이동 가능 영역에 포함된 그리드 중 일부를 인접한 그리드와 병합하여 확장함으로써 상기 맵 데이터를 조정하는 단계와, 상기 조정된 맵 데이터를 이용하여, 상기 이동 가능 영역을 통한 이동과 관련된 연산을 수행하는 단계를 포함할 수 있다. 몇몇 실시예들에서, 상기 맵 데이터를 조정하는 단계는 상기 맵 데이터의 모든 그리드 중 상기 확장된 그리드를 제외한 그리드에 대하여 조정 전 사이즈를 유지하는 단계를 포함할 수 있다. 또한, 다른 몇몇 실시예들에서, 상기 그리드는 단위 길이를 표현하는 것이고, 상기 맵 데이터를 이용한 맵 시각화 시 표시되지 않는 것일 수 있다.

몇몇 실시예들에서, 상기 맵 데이터를 조정하는 단계는 상기 이동 불가 영역을 이용하여 그리드 병합의 범위를 결정하는 단계를 포함할 수 있다. 또한, 상기 그리드 병합의 범위를 결정하는 단계는 상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록 그리드 병합의 범위를 결정하는 단계를 포함할 수 있다. 이하, 본 실시예들에서의 가능한 동작들을 설명한다.

상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록 그리드 병합의 범위를 결정하는 단계가 상기 이동 불가 영역 각각에 대하여, 다른 이동 불가 영역의 외곽선 또는 기 형성된 외곽선 확장선에 의하여 막힐 때까지 외곽선을 확장하는 단계를 반복하는 단계를 포함할 수 있다.

또한, 상기 이동 불가 영역은 복수개 이고, 상기 이동 불가 영역 중 적어도 일부는 직사각형 형상을 가지며, 상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록 그리드 병합의 범위를 결정하는 단계는 상기 복수의 이동 불가 영역을 제1 축 길이를 기준으로 오름차순으로 정렬하는 단계와 상기 정렬의 결과를 이용하여, 제1 축 길이가 짧은 이동 불가 영역부터 순차적으로 외곽선 확장을 수행하는 것을 반복하는 단계를 포함할 수도 있다. 이 때, 상기 이동 불가 영역 각각의 상기 제1 축의 길이의 분산값이 상기 이동 불가 영역 각각의 상기 제2 축의 길이의 분산값보다 큰 것일 수 있다. 또는, 상기 제1 축 길이가 짧은 이동 불가 영역부터 순차적으로 외곽선 확장을 수행하는 단계가 상기 제1 축 길이가 짧은 이동 불가 영역부터 순차적으로 제2 축 방향의 외곽선 확장을 수행하는 것을 반복하는 단계를 포함하고, 상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록 그리드 병합의 범위를 결정하는 단계는 상기 복수의 이동 불가 영역을 제2 축 길이를 기준으로 오름차순으로 정렬하는 단계와 상기 정렬의 결과를 이용하여 제2 축 길이가 짧은 이동 불가 영역부터 순차적으로 제1 축 방향의 외곽선 확장을 수행하는 것을 반복하는 단계를 포함할 수도 있다.

또한, 상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록 그리드 병합의 범위를 결정하는 단계는 병합 대상 그리드의 개수가 지정된 전체 최대 개수를 초과하지 않도록 그리드 병합의 범위를 결정하는 단계를 포함할 수도 있다. 이 때, 병합 대상 그리드의 개수가 지정된 최대 개수를 초과하지 않도록 그리드 병합의 범위를 결정하는 단계는 제1 축 상의 병합 대상 그리드의 개수가 지정된 제1 축 최대 개수를 초과하지 않도록 그리드 병합의 범위를 결정하는 단계를 포함할 수 있다.

또한, 상기 이동 가능 영역을 통한 이동과 관련된 연산을 수행하는 단계는 기준치 이상의 크기를 가진 상기 이동 가능 논리 구역 간의 이동을 포함하는 최적 이동 경로의 결정을 위한 연산을 수행하는 단계를 포함할 수 있다.

또한, 상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록, 그리드 병합의 범위를 결정하는 단계는 상기 이동 가능 논리 구역 중 비활성화 이동 가능 논리 구역을 선정하는 단계를 포함하고, 상기 이동 가능 영역을 통한 이동과 관련된 연산을 수행하는 단계는 상기 비활성화 이동 가능 논리 구역을 제외한 이동 가능 논리 구역 간의 이동을 포함하는 최적 이동 경로의 결정을 위한 연산을 수행하는 단계를 포함할 수 있다. 상기 맵 데이터는 창고의 맵 데이터이고, 상기 이동 불가 구역은 적치 구역이며, 상기 비활성화 이동 가능 논리 구역은, 상기 적치 구역에 바로 인접한 이동 가능 논리 구역 중, 상기 적치 구역의 투입구 측 이동 가능 논리 구역 이외의 이동 가능 논리 구역을 포함할 수 있다.

또한, 상기 연산을 수행하는 단계는 상기 이동 가능 논리 구역의 대표점 간의 이동을 포함하는 이동 경로들 중, 최소 길이를 가지는 이동 경로를 최적 이동 경로로 선정하는 단계를 포함할 수 있다.

한편, 상기 기술적 과제를 해결하기 위한 본 발명의 다른 실시예에 따른 맵 데이터를 이용한 이동 관련 연산 방법은, 이동 불가 영역을 포함하는 맵 데이터를 얻는 단계와, 상기 이동 불가 영역의 외곽선을 확장함으로써 복수의 이동 가능 논리 구역을 구획하는 단계와, 상기 복수의 이동 가능 논리 구역 간의 이동을 포함하는 이동 경로를 결정하는 단계를 포함할 수 있다.

몇몇 실시예들에서, 상기 복수의 이동 가능 논리 구역을 구획하는 단계는 상기 이동 불가 영역 각각에 대하여 다른 이동 불가 영역의 외곽선 또는 기 형성된 외곽선 확장선에 의하여 막힐때까지 외곽선을 확장하는 단계를 반복하는 단계를 포함할 수 있다.

다른 몇몇 실시예들에서, 상기 이동 불가 영역은 복수개이고, 상기 이동 불가 영역 중 적어도 일부는 직사각형 형상을 가지며, 상기 복수의 이동 가능 논리 구역을 구획하는 단계는 상기 복수의 이동 불가 영역을 제1 축 길이를 기준으로 오름차순으로 정렬하는 단계와, 상기 정렬의 결과를 이용하여 제1 축 길이가 짧은 이동 불가 영역부터 순차적으로 외곽선 확장을 수행하는 단계를 포함할 수 있다.

또 다른 몇몇 실시예들에서, 상기 이동 경로를 결정하는 단계는 상기 이동 가능 논리 구역의 대표점 간의 이동을 포함하는 이동 경로들 중, 최소 길이를 가지는 이동 경로를 상기 최적 이동 경로로 결정하는 단계를 포함할 수 있다.

상기 기술적 과제를 해결하기 위한, 본 발명의 또 다른 실시예에 따른 컴퓨팅 장치는, 이동 불가 영역을 포함하는 맵 데이터를 저장하는 스토리지 장치와, 컴퓨터 프로그램 및 상기 맵 데이터를 로드 하는 메모리와, 상기 컴퓨터 프로그램을 실행하는 프로세서를 포함할 수 있다. 이 때, 상기 컴퓨터 프로그램은 상기 이동 불가 영역의 외곽선을 확장함으로써 복수의 이동 가능 논리 구역을 구획하는 인스트럭션과, 상기 복수의 이동 가능 논리 구역 간의 이동을 포함하는 이동 경로를 결정하는 인스트럭션을 포함할 수 있다.

몇몇 실시예들에서, 상기 맵 데이터는 창고의 맵 데이터이고, 상기 이동 불가 구역은 적치 구역이며, 상기 컴퓨팅 장치는 상기 최적 이동 경로에 따라 이동하도록 제어되는 구동 수단을 더 포함할 수 있다.

다른 몇몇 실시예들에서, 상기 스토리지 장치는 상기 맵 데이터의 조정 룰 데이터를 더 저장하고, 상기 복수의 이동 가능 논리 구역을 구획하는 인스트럭션은 상기 조정 룰 데이터를 이용하여, 상기 이동 불가 영역의 외곽선을 확장함으로써 복수의 이동 가능 논리 구역을 구획하는 인스트럭션을 포함할 수 있다.

상기 기술적 과제를 해결하기 위한, 본 발명의 또 다른 실시예에 따른 컴퓨팅 장치는, 이동 불가 영역을 포함하는 맵 데이터로서, 상기 이동 불가 영역의 외곽선이 확장됨으로써 복수의 이동 가능 논리 구역이 구획된 맵 데이터를 저장하는 스토리지 장치와, 컴퓨터 프로그램 및 상기 맵 데이터를 로드 하는 메모리와, 상기 컴퓨터 프로그램을 실행하는 프로세서를 포함할 수 있다. 이 때, 상기 컴퓨터 프로그램은 상기 복수의 이동 가능 논리 구역 간의 이동을 포함하는 이동 경로를 결정하는 인스트럭션을 포함할 수 있다.

도 1 내지 도 3은 본 발명의 일 실시예에 따른 맵 데이터 기반 서비스 시스템의 구성도들이다.
도 4 내지 도 7은 본 발명의 몇몇 실시예들에 따른 효과를 설명하기 위한 도면들이다.
도 8은 본 발명의 다른 실시예에 따른 맵 데이터를 이용한 이동 관련 연산 방법의 순서도이다.
도 9는 도 8을 참조하여 설명한 이동 가능 논리 구역 형성 동작을 보다 상세히 설명하기 위한 순서도이다.
도 10a 내지 도 11b는 도 9를 참조하여 일부 동작을 보다 상세히 설명하기 위한 도면들이다.
도 12는 도 8을 참조하여 설명한 이동 가능 논리 구역 형성 동작을 보다 상세히 설명하기 위한 다른 순서도이다.
도 13a 및 도 13b는 도 12를 참조하여 일부 동작을 보다 상세히 설명하기 위한 도면들이다.
도 14는 도 8을 참조하여 설명한 이동 가능 논리 구역 형성 동작을 보다 상세히 설명하기 위한 또 다른 순서도이다.
도 15는 도 8을 참조하여 설명한 방법의 일부 변형 실시예에 따른 방법을 설명하기 위한 순서도이다.
도 16a 내지 도 17b는 도 15를 참조하여 설명한 일부 동작을 보다 상세히 설명하기 위한 도면들이다.
도 18은 본 발명의 또 다른 실시예에 따른 컴퓨팅 장치의 예시적인 하드웨어 구성도이다.

이하, 첨부된 도면을 참조하여 본 발명의 실시예들을 상세히 설명한다. 본 발명의 이점 및 특징, 그리고 그것들을 달성하는 방법은 첨부되는 도면과 함께 상세하게 후술되어 있는 실시예들을 참조하면 명확해질 것이다. 그러나 본 발명의 기술적 사상은 이하의 실시예들에 한정되는 것이 아니라 서로 다른 다양한 형태로 구현될 수 있으며, 단지 이하의 실시예들은 본 발명의 기술적 사상을 완전하도록 하고, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 본 발명의 범주를 완전하게 알려주기 위해 제공되는 것이며, 본 발명의 기술적 사상은 청구항의 범주에 의해 정의될 뿐이다.

각 도면의 구성요소들에 참조부호를 부가함에 있어서, 동일한 구성요소들에 대해서는 비록 다른 도면상에 표시되더라도 가능한 한 동일한 부호를 가지도록 하고 있음에 유의해야 한다. 또한, 본 발명을 설명함에 있어, 관련된 공지 구성 또는 기능에 대한 구체적인 설명이 본 발명의 요지를 흐릴 수 있다고 판단되는 경우에는 그 상세한 설명은 생략한다.

다른 정의가 없다면, 본 명세서에서 사용되는 모든 용어(기술 및 과학적 용어를 포함)는 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자에게 공통적으로 이해될 수 있는 의미로 사용될 수 있다. 또 일반적으로 사용되는 사전에 정의되어 있는 용어들은 명백하게 특별히 정의되어 있지 않는 한 이상적으로 또는 과도하게 해석되지 않는다. 본 명세서에서 사용된 용어는 실시예들을 설명하기 위한 것이며 본 발명을 제한하고자 하는 것은 아니다. 본 명세서에서, 단수형은 문구에서 특별히 언급하지 않는 한 복수형도 포함한다.

또한, 본 발명의 구성 요소를 설명하는 데 있어서, 제1, 제2, A, B, (a), (b) 등의 용어를 사용할 수 있다. 이러한 용어는 그 구성 요소를 다른 구성 요소와 구별하기 위한 것일 뿐, 그 용어에 의해 해당 구성 요소의 본질이나 차례 또는 순서 등이 한정되지 않는다. 어떤 구성 요소가 다른 구성요소에 "연결", "결합" 또는 "접속"된다고 기재된 경우, 그 구성 요소는 그 다른 구성요소에 직접적으로 연결되거나 또는 접속될 수 있지만, 각 구성 요소 사이에 또 다른 구성 요소가 "연결", "결합" 또는 "접속"될 수도 있다고 이해되어야 할 것이다. 이하, 본 발명의 몇몇 실시예들에 대하여 첨부된 도면에 따라 상세하게 설명한다.

도 1 내지 도 3을 참조하여, 본 발명의 일 실시예에 따른 맵 데이터 기반 서비스 시스템의 구성 및 동작을 설명한다. 본 실시예에 따른 맵 데이터 기반 서비스 시스템은 서비스 서버(100) 및 하나 이상의 클라이언트(20a, 20b)를 포함할 수 있다.

도 1에 도시된 바와 같이, 서비스 서버(100)는 하나 이상의 서비스 대상 사이트(site)의 맵 데이터를 저장할 수 있다. 도 1은 상기 사이트가 창고(warehouse)인 경우이고, 서비스 서버(100)는 각 창고의 맵 데이터(100a, 100b, 100n)를 저장한다.

맵 데이터(map data)는 서비스 대상 사이트 내에서의 이동(moving)을 위해 참조되어야 하는 정보로 이해될 수 있을 것이다. 상기 맵 데이터는 이동 가능 영역을 가리키는 데이터 및 이동 불가 영역을 가리키는 데이터를 포함한다. 맵 데이터가 표현하는 서비스 대상 사이트 내에서의 이동을 하기 위하여는, 상기 이동 가능 영역 안에서 형성되는 이동 경로가 결정되어야 할 것이다. 상기 맵 데이터는 상기 이동 가능 영역 및 상기 이동 불가 영역이 클라이언트(20a, 20b) 및 서비스 서버(100)에 의하여 식별될 수 있도록 사전 정의된 포맷으로 구조화된 데이터이다. 따라서, 상기 맵 데이터가 특정 포맷의 것으로 한정되어 해석될 수 없음을 유의하여야 한다.

도 1에 도시된 예시에서, 창고 A(10a)에 위치한 클라이언트(20a)가 (x1, y1)에서 (x2, y2)로의 이동 경로를 조회하는 요청을 서비스 서버(100)에 송신하면, 서비스 서버(100)는 창고 A의 맵 데이터(100a)를 이용하여 (x1, y1)에서 (x2, y2)로의 이동 경로를 연산하고, 연산 된 이동 경로에 대한 정보를 클라이언트(20a)에 송신할 수 있다. 또한, 창고 B(10b)에 위치한 클라이언트(20b)가 (x3, y3)에서 (x4, y4)로의 이동 경로를 조회하는 요청을 서비스 서버(100)에 송신하면, 서비스 서버(100)는 창고 B의 맵 데이터(100b)를 이용하여 (x3, y3)에서 (x4, y4)로의 이동 경로를 연산하고, 연산 된 이동 경로에 대한 정보를 클라이언트(20b)에 송신할 수 있다.

도 1에는 서비스 서버(100)가 경로 정보를 제공하는 것으로 예시되어 있으나, 서비스 서버(100)는 상기 이동 가능 영역을 통한 이동과 관련된 다양한 연산을 수행할 수 있다. 예를 들어, 서비스 서버(100)는, 시작점과 끝점이 지정된 경우 이동 가부에 대한 연산을 수행할 수도 있고, 시작점과 끝점이 지정된 경우 최저 시간 소요 경로를 산출하기 위한 연산을 수행할 수도 있으며, 시작점과 끝점이 지정된 경우 최장 시간 소요 경로를 산출하기 위한 연산을 수행할 수도 있고, 시작점과 끝점이 지정된 경우 최단 거리 경로를 산출하기 위한 연산을 수행할 수도 있고, 시작점과 끝점이 지정된 경우 최장 거리 경로를 산출하기 위한 연산을 수행할 수도 있고, 시작점과 끝점이 지정된 경우 모든 이동 가능 경로를 산출하기 위한 연산을 수행할 수도 있을 것이다.

창고 A(10a)가 초대형 규모를 가지고 있다고 가정하면, 창고 A의 맵 데이터(100a)를 기반으로 최적의 이동 경로를 연산하는데 많은 연산 자원이 소요될 것이다. 이러한 점을 감안하여, 서비스 서버(100)는 창고 A의 맵 데이터(110a)가 최적화되도록 조정된 맵 데이터(미도시)를 이용하여 최적의 이동 경로를 연산할 수 있다.

예를 들어, 창고 A의 맵 데이터(110a)가 동일 크기의 그리드(grid)들로 표현된 이동 가능 영역 및 이동 불가 영역을 포함하는 데이터인 경우, 서비스 서버(100)는 상기 이동 가능 영역에 포함된 그리드 중 일부를 인접한 그리드와 병합하여 확장함으로써 상기 맵 데이터를 조정하고, 상기 조정된 맵 데이터를 이용하여, 상기 이동 가능 영역을 통한 이동과 관련된 연산을 수행할 수 있을 것이다.

또한, 창고 A의 맵 데이터(110a)가 이동 불가 영역을 포함하는 데이터인 경우, 서비스 서버(100)는 상기 이동 불가 영역의 외곽선을 확장함으로써 복수의 이동 가능 논리 구역을 구획하고, 상기 복수의 이동 가능 논리 구역 간의 이동을 포함하는 최적 이동 경로를 결정할 수도 있을 것이다.

몇몇 실시예들에서, 도 2에 도시된 바와 같이, 서비스 서버(100)는 창고 관리 시스템(Warehouse Management System; WMS)(30) 등 외부 장치로부터 맵 데이터 원본을 수신하고, 상기 맵 데이터 원본이 최적화 조정된 맵 데이터(111a, 111b, 111n)를 생성하는 맵 데이터 조정부(120)를 포함할 수 있다. 맵 데이터 조정부(120)가 맵 데이터(110a, 110b, 110n)가 최적화되도록 조정된 맵 데이터(미도시)를 이용하여 이동과 관련된 연산을 하는 다양한 실시예들은 자세히 후술하기로 한다.

서비스 서버(100)는 클라이언트(20a)의 맵 데이터 다운로드 요청에 응답하여, 조정된 맵 데이터(111a)를 송신해줄 수 있다. 후술하겠으나, 조정된 맵 데이터(111a)를 이용하는 경우 넓은 영역에서의 이동 관련 연산도 빠르게 수행할 수 있고, 그러므로 클라이언트(20a)에서 수행되는 최적 경로 자체 탐색 앱(20a-1)에서도 자체적으로 이동 관련 연산을 수행할 수 있다. 즉, 이러한 경우, 클라이언트(20a)와 서비스 서버(100) 간의 네트워크 연결이 없더라도 창고 A(10a) 내에서의 최적 이동 경로 탐색이 가능한 사용성 측면의 효과를 얻을 수 있다.

몇몇 실시예들에서, 도 3에 도시된 바와 같이, 클라이언트(20a-1)는 구동 수단을 구비한 구동형 컴퓨팅 장치일 수 있다. 예를 들어, 클라이언트(20a-1)는 창고 A(10a)에서 아이템을 입출고 하는 지능형 로봇일 수도 있을 것이다. 도 2를 참조하여 설명한 바와 같이, 클라이언트(20a-1)에서 수행되는 경로 자체 탐색 프로그램(미도시)은 서비스 서버(100)의 도움이 없이 자체적으로 이동 관련 연산을 수행할 수 있다.

상기 경로 자체 탐색 프로그램은 창고 A(10a)의 조정된 맵 데이터(111a)를 기반으로 이동 관련 연산을 수행한다. 서비스 서버(100)로부터 다운로드 되어 클라이언트(20a-1)에 저장된 조정된 맵 데이터(111a)는 이동 가능 구역이 확장된 이동 가능 논리 구역에 대한 정보를 포함하고 있다. 상기 경로 자체 탐색 프로그램은 상기 이동 가능 논리 구역 간의 이동을 포함하는 이동 경로를 산출할 수 있을 것이다.

이미 설명한 바와 같이, 이동 가능 논리 구역 간의 이동을 포함하는 이동 경로를 산출함으로써, 맵 데이터가 커버하는 대상 구역의 넓이가 넓어지더라도 연산량 증가의 부담이 경감될 수 있다. 따라서, 상기 경로 자체 탐색 프로그램은 서비스 서버(100)에 비하여 빈약한 연산자원을 보유하고 있는 클라이언트(20a-1)에서 수행되더라도 충분히 초대형 창고와 같은 넓은 영역에서의 이동 관련 연산을 수행할 수 있을 것이다.

이하, 본 발명의 몇몇 실시예들에 따른 효과를 도 4 내지 도 7을 참조하여 설명하기로 한다.

도 4는 가상의 창고의 맵 데이터이다. 상기 창고는 326m x 173.5m의 초대형 창고로서, 평치(yard), 랙(rack), 스테이징(staging), 도크(dock) 및 기타 구조물을 포함하여, 7081개의 영역으로 구성되어 있다고 가정한다. 이 때, 상기 창고에서 생성될 수 있는 경로의 수는 25,066,740 가지(7081 * 7080 / 2 )에 달한다. 이렇게 많은 경로 각각에 대하여 최적의 경로를 산정하는 것은 매우 많은 연산 자원을 요하게 될 것이다. 도 5를 참조하여 보다 구체적으로 설명한다.

그리드 기반의 창고 맵 데이터에서, A에서 B로 이동하는 경로를 산출하는 연산을 수행하는 상황(1100)을 전제하면, 그리드 한 칸마다 다음 이동 그리드를 검토하는 연산이 수행될 필요가 있다. 예를 들어, A의 출발 그리드에서 한칸 아래로 내려온 후, 다음 그리드를 결정해야 하는 상황(1101)이라면, 좌측, 우측 및 하측 방향의 그리드에 대한 검토가 필요할 것이다. 이러한 과정을 거쳐 A에서 B까지의 경로(1103)가 확정되려면 16회의 다음 그리드 결정 연산이 수행되어야 할 것이다.

도 5에 도시된 것은 창고 전체 영역이 20 x 15 로 그리드가 그리 많지 않으나, 실제의 초대형 창고인 경우 훨씬 많은 그리드가 표시될 것이고, 그렇다면 다음 그리드를 결정하는 연산의 수행 횟수도 창고의 사이즈 증가만큼 증가하게 될 것이다.

이 때 고려할 수 있는 것이, 실제의 창고 사이즈를 일률적으로 축소 보정(resizing)하는 것이다. 예를 들어, 도 6에 도시된 것과 같이, 원본 맵 데이터(1104)를 가로 1/2, 세로 1/2으로 축소한 맵 데이터(1105)를 얻을 수 있을 것이다. 그런데, 축소 보정 시, 통로(1140)가 사라지는 등의 왜곡이 발생하게 된다.

도 6과 달리, 본 발명의 몇몇 실시예들에서는 실제 공간의 왜곡을 가져오지 않으면서도 이동 관련 연산의 연산량 감소를 얻을 수 있다. 도 7에서는, 원본 맵 데이터를 이용한 이동 경로(1103)의 연산(40)과, 본 발명의 몇몇 실시예들에 따른 조정된 맵 데이터를 이용한 이동 경로(1111)의 연산(50)이 개념적으로 비교된다. 이하, 조정된 맵 데이터를 이용한 이동 경로 연산(50)의 과정을 대략적으로 설명한다.

먼저, 조정된 맵 데이터(1106)가 얻어진다. 조정된 맵 데이터를 얻는 방법은 자세히 후술될 것이다. 출발 영역 A(1107)에서 도착 영역 B(1112)을 잇는 이동 경로(1111)는 이동 가능 논리 구역의 순차적 연결에 의하여 얻어질 것이다. 따라서, 원본 맵 데이터를 이용한 이동 경로(1103)의 연산(40) 과정과 유사하게, 이동 가능 논리 구역 마다, 다음의 이동 방향을 결정하는 연산이 수행되게 된다. 다음의 이동 방향을 결정하기 위해, 알려진 최적 경로 산출 알고리즘들이 적용될 수 있다. 예를 들어,

예를 들어, 출발 영역 A(1107)에서 막 출발하여, 출발 영역 A(1107) 하단의 이동 가능 논리 구역(1108)이 현재 위치인 경우, 다음으로 이동 가능한 이동 가능 논리 구역은 좌측 및 우측 이동 가능 논리 구역(1109, 1110)이고, 두개의 이동 가능 논리 구역 중 하나를 선정하게 될 것이다. 동일한 과정을 거쳐 총 5번의 이동 방향 결정 연산을 수행하면 도착 영역 B(1112)에 도달하게 된다.

원본 맵 데이터의 그리드 각각은 그 크기가 크지 않은 반면, 조정된 맵 데이터(1106)의 이동 가능 논리 구역 각각은 그 크기가 그리드 대비 더 크다. 따라서, 단순히 이동 가능 논리 구역의 식별자를 순차적으로 열거하는 것만으로는 이동 경로가 정확하게 특정되기 어려울 수 있을 것이다. 따라서, 몇몇 실시예들에서, 이동 경로는 각각의 이동 가능 논리 구역의 대표점의 순차적 연결으로 정의될 수도 있을 것이다. 상기 대표점은, 예를 들어 이동 가능 논리 구역의 중심점일 수 있다.

도 7의 예시적 상황에서, 원본 맵 데이터를 이용한 이동 경로 연산(40)이 16회의 이동 방향 결정 연산을 수행하는 반면, 조정된 맵 데이터를 이용한 이동 경로 연산(50)이 5회의 이동 방향 결정 연산을 수행한다. 동일한 상황에서, 약 30%의 연산만으로 이동 경로의 연산이 완료되는 연산량 경감의 효과를 확인할 수 있을 것이다. 또한, 단일 그리드 대비 더 큰 영역을 가지는 이동 가능 논리 구역의 대표점들이 연결되어 이동 경로가 형성됨으로써, 이동 방향이 불필요하게 직각방향으로 강제되지 않을 것이므로, 그에 따른 이동 거리 단축의 효과도 얻을 수 있을 것이다.

이하, 도 8을 참조하여, 본 발명의 다른 실시예에 따른 맵 데이터를 이용한 이동 관련 연산 방법(이하, '이동 관련 연산 방법')을 설명하기로 한다. 본 실시예에 따른 이동 관련 연산 방법은 컴퓨팅 장치에 의하여 수행될 수 있다. 본 실시예에 따른 이동 관련 연산 방법에 속하는 일부 동작을 설명함에 있어, 그 주체에 대한 기재가 생략된 경우, 그 주체는 상기 컴퓨팅 장치인 것으로 이해될 것 수 있을 것이다.

상기 컴퓨팅 장치는, 서버, 데스크탑 피씨, 노트북 피씨, 태블릿 피씨, 스마트폰 등 연산 수단을 포함하는 모든 기기를 의미하며, 예를 들어 산출된 최적 이동 경로에 따라 이동하도록 제어되는 구동 수단을 포함하는 지능형 로봇일 수도 있다. 또한, 클라이언트의 요청에 응답하여 상기 서비스 서버가 이동 관련 연산을 수행하는 경우, 상기 컴퓨팅 장치는 도 1 내지 도 3을 참조하여 설명한 서비스 서버일 수도 있다. 또한, 클라이언트가 맵 데이터를 다운로드 한 후, 다운로드 된 맵 데이터를 조정하며, 조정된 맵 데이터를 이용하여 자체적으로 이동 관련 연산을 수행할 수도 있는 바, 이러한 경우 상기 컴퓨팅 장치는 상기 클라이언트가 될 것이다. 도 8을 참조하여 설명한다.

단계 S101에서, 맵 데이터가 얻어진다. 상기 맵 데이터는 디지털 데이터로서, 서비스 대상 사이트 내에서의 이동(moving)을 위해 참조되어야 하는 정보이며, 상기 맵 데이터는 이동 가능 영역을 가리키는 데이터 및 이동 불가 영역을 가리키는 모든 형태의 데이터이다. 예를 들어, 상기 맵 데이터는 동일 크기의 그리드들로 표현되는 것일 수 있다.

상기 이동 가능 영역은, 말그대로 이동이 가능한 영역이다. 따라서, 상기 맵 데이터가 표현하는 사이트(site)의 출발지점에서 도착지점까지의 이동에 대한 연산은, 상기 이동 가능 영역만을 통하여 도착지점에 이르는 것과 관련된 연산이 될 것이다. 예를 들어, 상기 이동 가능 영역은 상기 이동 불가 영역 이외의 모든 영역으로 정의될 수 있을 것이다. 이 때, 상기 이동 가능 영역은 상기 이동 불가 영역의 그리드를 제외한 모든 그리드로 정의될 수 있을 것이다.

단계 S103에서, 이동 가능 논리 구역이 형성된다. 이 때, 상기 이동 가능 영역이 복수의 상기 이동 가능 논리 구역으로 구획되는 것으로 이해될 수 있을 것이다. 예를 들어, 상기 이동 불가 영역의 외곽선이 확장됨으로써 복수의 이동 가능 논리 구역이 형성될 수 있을 것이다.

상기 맵 데이터가 그리드 기반의 맵 데이터인 경우, 상기 이동 가능 영역에 포함된 그리드 중 일부가 인접한 그리드와 병합하여 확장됨으로써 상기 이동 가능 논리 구역이 형성될 수 있다. 이 때, 상기 이동 불가 영역을 이용하여 그리드 병합의 범위가 결정될 수 있다. 예를 들어, 상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록, 그리드 병합의 범위가 결정될 수 있다. 상기 그리드는, 맵 데이터의 시각화 또는 렌더링의 결과로 디스플레이되는 것일 수도 있고, 디스플레이되지 않는 것일 수도 있다. 즉, 상기 그리드는 보여주기 위한 데이터가 아니고, 가로/세로 거리를 표시하는 데이터에 불과할 수도 있다.

또한, 이동 가능 영역에 포함된 그리드 중 일부가 인접한 그리드와 병합하여 확장되는 것이고, 상기 맵 데이터의 모든 그리드 중 상기 확장된 그리드를 제외한 그리드는 조정 전 사이즈가 유지되므로, 상기 맵 데이터의 각 그리드를 일률적으로 리사이징(resizing)하는 것은 아님을 유의한다.

다음으로, 단계 S105에서, 상기 이동 가능 논리 구역을 이용하여, 상기 이동 가능 영역을 통한 이동과 관련된 연산이 수행되고, 그 결과가 출력된다(S107). 예를 들어, 시작점과 끝점이 지정된 경우 이동 가부, 최저 시간 소요 경로, 최장 시간 소요 경로, 최단 거리 경로, 최장 거리 경로 및 모든 이동 가능 경로 중 적어도 하나가 상기 결과로서 디스플레이 되거나, 결과 데이터가 요청측 장치로 송신될 수 있을 것이다.

이하, 도 9 내지 도 10b를 참조하여, 단계 S103을 보다 상세히 설명한다.

단계 S1310에서, 이동 불가 영역의 외곽선이 확장된다. 도 10a의 맵 데이터(1113)를 통하여 표현된 이동 불가 영역(1114)의 외곽선 확장 결과가, 도 10b에 도시된다. 맵 데이터(1113)가 총 10개의 적치공간인 이동 불가 영역을 표현하고 있는 것으로 이해될 수 있을 것이다. 이동 불가 영역(1114)의 외곽선이 확장된 선(1115a, 1115b, 1115c, 1115d, 1115e)은, 다른 이동 불가 영역의 외곽선에 닿거나, 맵 데이터(1113) 전체의 외곽선에 닿거나, 기 형성된 외곽선확장선에 닿을 때까지 확장될 수 있다.

다음으로, 단계 S1320에서, 이동 불가 영역의 외곽선과 상기 확장된 외곽선에 의하여 형성되는 이동 가능 논리 구역이 식별된다. 도 10c는 이동 불가 영역(1114)의 외곽선과 외곽선 확장선에 의하여 형성된 이동 가능 논리 구역(1116a, 1116b, 1116c)을 도시한다.

단계 S1310과 단계 S1320은 맵 데이터(1113)에 포함된 모든 이동 불가 영역에 대하여 반복 수행될 수 있다. 도 10d에는, 맵 데이터(1113)에 포함된 모든 이동 불가 영역에 대하여 단계 S1310과 단계 S1320이 형성된 결과로 형성된 이동 가능 논리 구역들을 도시한다.

도 10d에는 이동 가능 논리 구역의 외곽선 및 확장된 외곽선에 의하여 형성되는 영역이 비어 있는 것이 도시된다. 단계 S1330에서, 이동 가능 논리 구역의 외곽선 및 확장된 외곽선에 의하여 형성되는 영역 또한 이동 가능 논리 구역으로 추가 식별된다. 도 10e에는, 단계 S1330에서 추가 식별된 이동 가능 논리 구역(1117a, 1117b, 1117c, 1117d, 1117e, 1117f)이 도시된다.

단계 S1310 내지 S1330을 통하여 이동 가능 논리 구역이 식별되는 점이 도시되었다. 도 10a 내지 도 10e의 맵 데이터(1113)에는 그리드가 도시되지 않았으나, 가로/세로 최소 단위 길이로 구성되는 그리드로서, 맵 데이터(1113)의 이동 가능 구역 및 이동 불가 구역이 표현될 수 있음은 물론이다.

그리고, 도 10a 내지 도 10e를 참조하여 설명된 모든 이동 가능 논리 구역(1116a, 1116b, 1116c, 1117a, 1117b, 1117c, 1117d, 1117e, 1117f)은, 결과적으로 이동 가능 논리 구역 내부의 모든 그리드들이 하나로 병합됨으로써 형성되는 것으로 이해될 수도 있을 것이다. 즉, 이동 가능 논리 구역의 식별은, 이동 가능 논리 구역에 포함된 그리드들의 병합의 범위를 결정하는 것으로 이해될 수 있을 것이다.

다음으로, 식별된 이동 가능 논리 구역의 크기가 최소 크기 이상 및 최대 크기 미만의 정상 범위에 속하지 않는 경우, 예외 처리가 진행될 수 있다. 단계 S1340에서, 최소 크기 미만의 크기를 가지는 이동 가능 논리 구역은 삭제된다. 너무 작은 구역은 어차피 이동이 불가능하여 삭제되는 것이 바람직하다. 또한, 단계 S1340에서, 최대 크기 이상의 크기를 가지는 이동 가능 논리 구역에 대하여는, 하나의 이동 가능 논리 구역이 과도한 영역을 점유하는 것을 방지하기 위해, 그 크기가 축소 조정된다. 예를 들어, 도 16a는 이동 불가 영역 A(1125) 및 이동 불가 영역 B(1127)에 인접한 이동 가능 논리 구역 1, 2(1126a, 1126b)를 도시한다. 도 16a에 도시된 이동 가능 논리 구역 1(1126a)은 가로 길이가 기준치를 초과하게 되어, 도 16b와 같이 조정될 것이다(1126b). 또한, 도 16a에 도시된 이동 가능 논리 구역 2(1128)도 도 16b와 같이 삭제될 것이다.

몇몇 실시예들에서, 상기 최소 크기 및 상기 최대 크기는 넓이 단위로 지정될 수 있다.

다른 몇몇 실시예에서, 상기 최소 크기 및 상기 최대 크기는 가로 길이 또는 세로 길이로 지정될 수 있다.

도 10a 내지 도 10e에서 도시된 사례에 따르면, 이동 불가 영역 10개의 형상이 모두 동일하였으나, 실제의 공간은 이동 불가 영역 각각의 형상이 서로 다를 수 있을 것이다. 이러한 경우, 이동 불가 영역에 인접한 이동 가능 논리 구역을 식별해주는 순서에 따라, 이동 가능 논리 구역이 다르게 형성될 수 있다. 관련 하여 도 11a 내지 도 11b를 참조하여 설명한다.

도 11a의 맵 데이터(1118)에는, 이동 불가 영역 A(1119a), 이동 불가 영역 B(1119b), 이동 불가 영역 C(1119c) 및 이동 불가 영역 D(1119d)가 각각 표현된다. 4개의 이동 불가 영역(1119a, 1119b, 1119c, 1119d) 모두 가로 길이는 W1으로 동일하고, 이동 불가 영역 A(1119a)의 세로 길이는 H1으로 나머지 이동 불가 영역들(1119b, 1119c, 1119d)의 세로 길이인 H2보다 더 길다고 가정하자.

도 11a에 도시된 맵 데이터(1118)를 이용하여, 이동 불가 영역 A(1119a), 이동 불가 영역 B(1119b), 이동 불가 영역 C(1119c) 및 이동 불가 영역 D(1119d)의 순서로 이동 가능 논리 구역이 식별 로직이 수행되면, 총 5개의 이동 가능 논리 구역(1120a, 1120b, 1120c, 1120d, 1120e)이 형성될 것이다.

그런데, 이동 불가 영역 A(1119a)의 우측에 위치한 이동 가능 논리 구역(1120b)은, 그 우측에 세개의 서로 다른 이동 불가 영역(1119b, 1119c, 1119d)이 존재함에도 불구하고 하나의 통합된 이동 가능 논리 구역이 형성된 것이다. 세로 길이를 기준으로 오름 차순으로 각 이동 불가 영역(1119a, 1119b, 1119c, 1119d)을 정렬하고, 정렬된 순서로 이동 가능 논리 구역 식별 로직이 수행되는 것에 의하여, 이동 가능 논리 구역이 다르게 형성될 수 있다.

즉, 도 11a 및 도 11b에 도시된 상황의 경우, 세로 길이를 기준으로 오름 차순으로 정렬된 순서, 즉 이동 불가 영역 B(1119b), 이동 불가 영역 C(1119c), 이동 불가 영역 D(1119d) 및 이동 불가 영역 A(1119a)의 순서로 이동 가능 논리 구역이 식별 로직이 수행되면, 총 7개의 이동 가능 논리 구역(1120a, 1120c, 1120d, 1120e, 1120f, 1120g, 1120h)이 형성될 것이다.

도 11a 내지 도 11b에서 살핀 바와 같이, 작은 크기의 이동 불가 영역에 대하여 먼저 이동 가능 논리 구역 형성 로직을 수행해 줌으로써, 부적절하게 넓은 이동 가능 논리 구역이 형성되는 것을 방지할 수 있다. 몇몇 실시예에서, 상기 이동 불가 영역의 크기는, 상기 이동 불가 영역의 넓이를 가리킬 수 있다.

이하, 작은 크기의 이동 불가 영역에 대하여 먼저 이동 가능 논리 구역 형성 로직을 수행해주는 것과 관련된 몇몇 실시예들을 설명한다.

도 12를 참조하면, 제1 축 길이 기준의 정렬 결과에 따른 이동 가능 논리 구역 형성 및 제2 축 길이 기준의 정렬 결과에 따른 이동 가능 논리 구역 형성이 모두 진행될 수 있다.

복수의 이동 불가 영역이 가로 길이를 기준으로 오름차순으로 정렬되고(S1300), 정렬된 순서로 각 이동 불가 영역에 대하여 세로 방향 외곽선 확장을 통해 이동 가능 논리 구역 형성이 되고(S1301, S1302), 또한, 복수의 이동 불가 영역이 세로 길이를 기준으로 오름차순으로 정렬되고(S1303), 정렬된 순서로 각 이동 불가 영역에 대하여 가로 방향 외곽선 확장을 통해 이동 가능 논리 구역 형성(S1304, S1305)이 되는 것이 병렬적으로 진행될 수도 있다.

이와 관련하여, 도 13a 및 도 13b에 도시된 맵 데이터(1121)를 참조하여 설명한다. 도 13a에는, 세로 길이를 기준으로 오름 차순 정렬된 이동 불가 영역 각각에 대하여 가로 방향의 외곽선 확장에 의하여 이동 가능 논리 구역(1122)이 형성된 결과가 도시된다. 이동 가능 논리 구역(1122)은 제1 해칭 표시되어 있고, 그 형성 순서가 표시되어 있다. 또한, 도 13b에는, 가로 길이를 기준으로 오름 차순 정렬된 이동 불가 영역 각각에 대하여 세로 방향의 외곽선 확장에 의하여 이동 가능 논리 구역(1123)이 형성된 결과가 도시된다. 이동 가능 논리 구역(1122)은 제2 해칭 표시되어 있고, 그 형성 순서가 표시되어 있다.

도 13a 내지 도 13b에 도시된 바와 같이, 제1 축 길이 기준의 정렬 결과에 따른 이동 가능 논리 구역 형성 및 제2 축 길이 기준의 정렬 결과에 따른 이동 가능 논리 구역 형성이 모두 진행됨으로써, 이동 가능 논리 구역을 누락 없이 형성시켜 줄 수 있는 효과를 얻을 수 있을 것이다.

또한, 제1 축 길이 기준의 정렬 결과에 따른 이동 가능 논리 구역 형성 및 제2 축 길이 기준의 정렬 결과에 따른 이동 가능 논리 구역 형성 중 어느 하나만 진행될 수도 있다. 이와 관련하여, 도 14를 참조하여 설명한다.

단계 S1306에서, 제1 축 및 제2 축 중 어느 한 축이 선정되고, 선정된 축의 길이를 기준으로 하여, 복수의 이동 불가 영역에 대한 오름 차순 정렬이 수행된다.

이 때, 제1 축 및 제2 축 중, 제1 축의 이동 불가 영역 길이가 제2 축에 비하여 다양하게 분포되어 있다면, 제1 축의 길이 기준의 정렬 결과에 따른 이동 가능 논리 구역 형성이 수행될 수 있을 것이다. 즉, 제1 축의 이동 불가 영역 길이의 분산 값이 제2 축의 분산 값보다 큰 경우, 제1 축의 길이 기준의 정렬 결과에 따른 이동 가능 논리 구역 형성이 수행될 수 있을 것이다. 예를 들어, 도 11a 및 도 11b에 도시된 상황에서, 이동 불가 영역의 가로 길이는 모두 W1으로 동일하므로, 각 이동 불가 영역이 세로 길이를 기준으로 오름차순 정렬될 수 있다.

다음으로, 단계 S1307, 단계 S1308에서, 정렬 결과에 따른 순서대로, 각각의 이동 불가 영역에 대한 이동 가능 논리 구역 형성 로직이 수행된다. 이 때, 도 12의 S1301 및 S1304와 달리 각각의 이동 불가 영역에 대한 전방향의 외곽선 확장이 수행되는 점에 유의한다.

단계 S1330에서, 이동 가능 논리 구역의 외곽선 및 확장된 외곽선에 의하여 형성되는 영역 또한 이동 가능 논리 구역으로 추가 식별되고, 단계 S1340 내지 단계 S1350에서 이동 가능 논리 구역의 크기를 기반으로 한 에러 처리가 수행된다.

예를 들어, 복수의 이동 불가 영역이 제1 축 길이를 기준으로 오름차순으로 정렬되고, 상기 정렬의 결과를 이용하여, 제1 축 길이가 짧은 이동 불가 영역부터 순차적으로 외곽선 확장이 수행되는 것, 즉 상기 이동 가능 논리 구역 형성 로직이 수행되는 것이 반복될 수 있다. 상기 제1 축은, 제1 축의 길이의 분산값이 상기 이동 불가 영역 각각의 상기 제2 축의 길이의 분산값보다 크도록 결정될 수 있다. 이후, 정렬된 순서에 따라 상기 이동 가능 논리 구역 형성 로직이 수행될 수 있다.

다음으로, 도 15를 참조하여, 도 8을 참조하여 설명한 방법의 일부 변형 실시예에 따른 방법을 설명한다. 도 15에 도시된 순서도는, 도 8의 순서도 대비, 단계 S104를 더 포함하며, 단계 S105가 단계 S105-1로 대체되었다. 이하, 도 8 대비 변경된 부분을 위주로 설명한다.

단계 S104에서 비활성화 이동 가능 논리 구역이 선정된다. 상기 비 활성화 이동 가능 논리 구역은, 기 형성된 이동 가능 논리 구역 중, 다양한 이유로 이동 경로에 포함될 수 없는 이동 가능 논리 구역을 가리킨다.

예를 들어, 도 17a의 맵 데이터(118)에서, 이동 불가 영역인 적치 영역 A(1127)의 투입구(1128)가 상방으로 지정된 경우, 적치 영역 A(1127)의 근접 이동 가능 논리 구역들(해칭 표시) 중 적치 영역 A(1127)의 상방향 외곽선에 인접한 2개의 이동 가능 논리 구역들(1129a, 1129b)을 제외한 나머지 이동 가능 논리 구역들(1130 포함)은 모두 비활성화 이동 가능 논리 구역으로 선정될 것이다. 어차피 적치 영역 A(1127)의 좌측, 우측, 하방향으로는 입고 및 출고를 할 수 없으므로, 이동 경로에 포함될 수 없기 때문이다. 이에 따라, 도 17b에는 비활성화 이동 가능 논리 구역이 모두 점선으로 표시되어 있다.

지금까지 설명된 방법에 따라, 이동 경로로 고려될 수 있는 이동 가능 논리 구역들 만을 고려하여 이동 경로가 결정됨으로써, 연산량이 획기적으로 감소될 수 있을 것이다.

도 18은 본 발명의 다양한 실시예에서 컴퓨팅 장치를 구현할 수 있는 예시적인 하드웨어 구성도이다. 본 실시예에 따른 컴퓨팅 장치(1000)는 하나 이상의 프로세서(150), 시스템 버스, 통신 인터페이스(170), 프로세서(150)에 의하여 수행되는 컴퓨터 프로그램(190)을 로드(load)하는 메모리(160)와, 컴퓨터 프로그램(190)를 저장하는 스토리지(180)를 포함할 수 있다. 도 18에는 본 발명의 실시예와 관련 있는 구성요소들만이 도시되어 있다. 따라서, 본 발명이 속한 기술분야의 통상의 기술자라면 도 18에 도시된 구성요소들 외에 다른 범용적인 구성 요소들이 더 포함될 수 있음을 알 수 있다.

프로세서(150)는 컴퓨팅 장치(1000)의 각 구성의 전반적인 동작을 제어한다. 프로세서(150)는 CPU(Central Processing Unit), MPU(Micro Processor Unit), MCU(Micro Controller Unit), GPU(Graphic Processing Unit) 또는 본 발명의 기술 분야에 잘 알려진 임의의 형태의 프로세서 중 적어도 하나를 포함하여 구성될 수 있다. 또한, 프로세서(150)는 본 발명의 다양한 실시예들에 따른 방법/동작을 실행하기 위한 적어도 하나의 애플리케이션 또는 프로그램에 대한 연산을 수행할 수 있다. 컴퓨팅 장치(1000)는 하나 이상의 프로세서를 구비할 수 있다.

메모리(160)는 각종 데이터, 명령 및/또는 정보를 저장한다. 메모리(160)는 본 발명의 다양한 실시예들에 따른 방법/동작들을 실행하기 위하여 스토리지(180)로부터 하나 이상의 프로그램(190)을 로드(load) 할 수 있다. 메모리(160)의 예시는 RAM이 될 수 있으나, 이에 한정되는 것은 아니다.

상기 시스템 버스는 컴퓨팅 장치(1000)의 구성 요소 간 통신 기능을 제공한다. 상기 버스는 주소 버스(Address Bus), 데이터 버스(Data Bus) 및 제어 버스(Control Bus) 등 다양한 형태의 버스로 구현될 수 있다.

통신 인터페이스(170)는 컴퓨팅 장치(1000)의 유무선 인터넷 통신을 지원한다. 통신 인터페이스(170)는 인터넷 통신 외의 다양한 통신 방식을 지원할 수도 있다. 이를 위해, 통신 인터페이스(170)는 본 발명의 기술 분야에 잘 알려진 통신 모듈을 포함하여 구성될 수 있다. 통신 인터페이스(170)는 하나 이상의 블록체인 노드(200) 및 하나 이상의 스토리지 노드(400)를 연결 할 수 있다.

스토리지(180)는 하나 이상의 컴퓨터 프로그램(190)을 비임시적으로 저장할 수 있다. 스토리지(180)는 플래시 메모리 등과 같은 비휘발성 메모리, 하드 디스크, 착탈형 디스크, 또는 본 발명이 속하는 기술 분야에서 잘 알려진 임의의 형태의 컴퓨터로 읽을 수 있는 기록 매체를 포함하여 구성될 수 있다.

컴퓨터 프로그램(190)은 본 발명의 다양한 실시예들에 따른 방법/동작들이 구현된 하나 이상의 인스트럭션들을 포함할 수 있다. 컴퓨터 프로그램(190)이 메모리(160)에 로드 되면, 프로세서(150)는 상기 하나 이상의 인스트럭션들을 실행시킴으로써 본 발명의 다양한 실시예들에 따른 방법/동작들을 수행할 수 있다.

컴퓨터 프로그램(190)은, 상기 이동 불가 영역의 외곽선을 확장함으로써 복수의 이동 가능 논리 구역을 구획하는 인스트럭션과, 상기 복수의 이동 가능 논리 구역 간의 이동을 포함하는 이동 경로를 결정하는 인스트럭션을 포함할 수 있다. 또한, 상기 맵 데이터는 창고의 맵 데이터이고, 상기 이동 불가 구역은 적치 구역이며, 컴퓨팅 장치(1000)는 상기 최적 이동 경로에 따라 이동하도록 제어되는 구동 수단(미도시)을 더 포함할 수 있다.

또한, 몇몇 실시예들에서, 스토리지(180)는 이동 불가 영역을 포함하는 맵 데이터로서, 상기 이동 불가 영역의 외곽선이 확장됨으로써 복수의 이동 가능 논리 구역이 구획된 맵 데이터를 저장할 수 있다. 즉, 이미 조정된 상태의 맵 데이터가 다운로드 받아 저장된 것일 수 있다.

이 때, 컴퓨터 프로그램(190)은, 상기 복수의 이동 가능 논리 구역 간의 이동을 포함하는 이동 경로를 결정하는 인스트럭션을 포함할 수 있다.

지금까지 도 1 내지 도 17을 참조하여 설명된 본 발명의 기술적 사상은 컴퓨터가 읽을 수 있는 매체 상에 컴퓨터가 읽을 수 있는 코드로 구현될 수 있다. 상기 컴퓨터로 읽을 수 있는 기록 매체는, 예를 들어 이동형 기록 매체(CD, DVD, 블루레이 디스크, USB 저장 장치, 이동식 하드 디스크)이거나, 고정식 기록 매체(ROM, RAM, 컴퓨터 구비 형 하드 디스크)일 수 있다. 상기 컴퓨터로 읽을 수 있는 기록 매체에 기록된 상기 컴퓨터 프로그램은 인터넷 등의 네트워크를 통하여 다른 컴퓨팅 장치에 전송되어 상기 다른 컴퓨팅 장치에 설치될 수 있고, 이로써 상기 다른 컴퓨팅 장치에서 사용될 수 있다.

이상 첨부된 도면을 참조하여 본 발명의 실시예들을 설명하였지만, 본 발명이 속하는 기술분야에서 통상의 지식을 가진 자는 그 기술적 사상이나 필수적인 특징을 변경하지 않고서 본 발명이 다른 구체적인 형태로도 실시될 수 있다는 것을 이해할 수 있다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적인 것이 아닌 것으로 이해해야만 한다. 본 발명의 보호 범위는 아래의 청구범위에 의하여 해석되어야 하며, 그와 동등한 범위 내에 있는 모든 기술 사상은 본 발명에 의해 정의되는 기술적 사상의 권리범위에 포함되는 것으로 해석되어야 할 것이다.

Claims (23)

1. 컴퓨팅 장치에 의하여 수행되는 방법에 있어서,
   동일 크기의 그리드(grid)들로 표현된 이동 가능 영역 및 이동 불가 영역을 포함하는 맵 데이터를 얻는 단계;
   상기 이동 가능 영역에 포함된 그리드 중 일부를 인접한 그리드와 병합하여 확장함으로써 상기 맵 데이터를 조정하는 단계; 및
   상기 조정된 맵 데이터를 이용하여, 상기 이동 가능 영역을 통한 이동과 관련된 연산을 수행하는 단계를 포함하고,
   상기 맵 데이터를 조정하는 단계는,
   상기 이동 불가 영역을 이용하여, 그리드 병합의 범위를 결정하는 단계를 포함하고,
   상기 그리드 병합의 범위를 결정하는 단계는,
   상기 이동 불가 영역의 외곽선 확장선에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록, 그리드 병합의 범위를 결정하는 단계를 포함하는,
   맵 데이터를 이용한 이동 관련 연산 방법.
2. 제1 항에 있어서,
   상기 맵 데이터를 조정하는 단계는,
   상기 맵 데이터의 모든 그리드 중 상기 확장된 그리드를 제외한 그리드에 대하여 조정 전 사이즈를 유지하는 단계를 포함하는,
   맵 데이터를 이용한 이동 관련 연산 방법.
3. 제1 항에 있어서,
   상기 그리드는,
   단위 길이를 표현하는 것이고, 상기 맵 데이터를 이용한 맵 시각화 시 표시되지 않는 것인,
   맵 데이터를 이용한 이동 관련 연산 방법.
4. 삭제
5. 삭제
6. 제1 항에 있어서,
   상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록, 그리드 병합의 범위를 결정하는 단계는,
   상기 이동 불가 영역 각각에 대하여, 다른 이동 불가 영역의 외곽선 또는 기 형성된 외곽선 확장선에 의하여 막힐때까지 외곽선을 확장하는 단계를 반복하는 단계를 포함하는,
   맵 데이터를 이용한 이동 관련 연산 방법.
7. 제1 항에 있어서,
   상기 이동 불가 영역은 복수개 이고, 상기 이동 불가 영역 중 적어도 일부는 직사각형 형상을 가지며,
   상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록, 그리드 병합의 범위를 결정하는 단계는,
   상기 복수의 이동 불가 영역을 제1 축 길이를 기준으로 오름차순으로 정렬하는 단계; 및
   상기 정렬의 결과를 이용하여, 제1 축 길이가 짧은 이동 불가 영역부터 순차적으로 외곽선 확장을 수행하는 것을 반복하는 단계를 포함하는,
   맵 데이터를 이용한 이동 관련 연산 방법.
8. 제7 항에 있어서,
   상기 제1 축 길이가 짧은 이동 불가 영역부터 순차적으로 외곽선 확장을 수행하는 단계는,
   상기 제1 축 길이가 짧은 이동 불가 영역부터 순차적으로 제2 축 방향의 외곽선 확장을 수행하는 것을 반복하는 단계를 포함하고,
   상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록, 그리드 병합의 범위를 결정하는 단계는,
   상기 복수의 이동 불가 영역을 제2 축 길이를 기준으로 오름차순으로 정렬하는 단계; 및
   상기 정렬의 결과를 이용하여, 제2 축 길이가 짧은 이동 불가 영역부터 순차적으로 제1 축 방향의 외곽선 확장을 수행하는 것을 반복하는 단계를 포함하는,
   맵 데이터를 이용한 이동 관련 연산 방법.
9. 제7 항에 있어서,
   상기 이동 불가 영역 각각의 상기 제1 축의 길이의 분산값이 상기 이동 불가 영역 각각의 제2 축의 길이의 분산값보다 큰 것을 특징으로 하는,
   맵 데이터를 이용한 이동 관련 연산 방법.
10. 제1 항에 있어서,
    상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록, 그리드 병합의 범위를 결정하는 단계는,
    병합 대상 그리드의 개수가 지정된 전체 최대 개수를 초과하지 않도록 그리드 병합의 범위를 결정하는 단계를 포함하는,
    맵 데이터를 이용한 이동 관련 연산 방법.
11. 제10 항에 있어서,
    병합 대상 그리드의 개수가 지정된 최대 개수를 초과하지 않도록 그리드 병합의 범위를 결정하는 단계는,
    제1 축 상의 병합 대상 그리드의 개수가 지정된 제1 축 최대 개수를 초과하지 않도록 그리드 병합의 범위를 결정하는 단계를 포함하는,
    맵 데이터를 이용한 이동 관련 연산 방법.
12. 제1 항에 있어서,
    상기 이동 가능 영역을 통한 이동과 관련된 연산을 수행하는 단계는,
    기준치 이상의 크기를 가진 상기 이동 가능 논리 구역 간의 이동을 포함하는 최적 이동 경로의 결정을 위한 연산을 수행하는 단계를 포함하는,
    맵 데이터를 이용한 이동 관련 연산 방법.
13. 제1 항에 있어서,
    상기 이동 불가 영역의 외곽선 확장에 의하여 형성되는 이동 가능 논리 구역에 포함되는 그리드들이 포함되도록, 그리드 병합의 범위를 결정하는 단계는,
    상기 이동 가능 논리 구역 중 비활성화 이동 가능 논리 구역을 선정하는 단계를 포함하고,
    상기 이동 가능 영역을 통한 이동과 관련된 연산을 수행하는 단계는,
    상기 비활성화 이동 가능 논리 구역을 제외한 이동 가능 논리 구역 간의 이동을 포함하는 최적 이동 경로의 결정을 위한 연산을 수행하는 단계를 포함하는,
    맵 데이터를 이용한 이동 관련 연산 방법.
14. 제13 항에 있어서,
    상기 맵 데이터는 창고의 맵 데이터이고,
    상기 이동 불가 구역은 적치 구역이며,
    상기 비활성화 이동 가능 논리 구역은, 상기 적치 구역에 바로 인접한 이동 가능 논리 구역 중, 상기 적치 구역의 투입구 측 이동 가능 논리 구역 이외의 이동 가능 논리 구역을 포함하는,
    맵 데이터를 이용한 이동 관련 연산 방법.
15. 제1 항에 있어서,
    상기 연산을 수행하는 단계는,
    상기 이동 가능 논리 구역의 대표점 간의 이동을 포함하는 이동 경로들 중, 최소 길이를 가지는 이동 경로를 최적 이동 경로로 선정하는 단계를 포함하는,
    맵 데이터를 이용한 이동 관련 연산 방법.
16. 삭제
17. 삭제
18. 삭제
19. 삭제
20. 삭제
21. 삭제
22. 삭제
23. 삭제