[논문]휴리스틱 탐색 기법을 이용한 네스팅 전문가 시스템

신동목

doi:10.5574/ksoe.2012.26.4.008

Abstract ▼ AI-Helper

Two dimensional nesting is a common problem in industries such as the shipbuilding, automotive, clothing, shoe-making, and furniture industries, in which various parts are cut off from stock or packed in a flat space while minimizing waste or unoccupied space. Nesting is known as an NP-complete prob...

Two dimensional nesting is a common problem in industries such as the shipbuilding, automotive, clothing, shoe-making, and furniture industries, in which various parts are cut off from stock or packed in a flat space while minimizing waste or unoccupied space. Nesting is known as an NP-complete problem, which has a solution time proportional to the superpolynomial of the input size. It becomes practically impossible to find an optimal solution using algorithmic methods as the number of shapes to nest increases. Therefore, heuristic methods are commonly used to solve nesting problems. This paper presents an expert system that uses a heuristic search method based on an evaluation function for nesting problems, in which parts and stock are represented by pixels. The system is developed in CLIPS, an expert system shell, and is applied to four different kinds of example problems to verify its applicability in practical problems.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

본 논문에서는 네스팅 문제를 휴리스틱 기법을 이용한 깊이 우선 트리 탐색 문제로 정의한다. Fig.
본 연구에서는 미 항공우주국(NASA)에서 개발한 전문가 시스템 쉘(Shell)인 CLIPS(http://clipsrules.sourceforge.net/)를 이용하여 네스팅을 위한 전문가 시스템을 휴리스틱 탐색 방법을 이용하여 구축하며 이를 블록 맞추기 퍼즐, 일반 네스팅, 조선 분야 네스팅, 이형 경계 형상 소재에의 배치 문제에 적용하여 그 적용 가능성을 예시하고자 한다.
본 연구에서는 지식기반 추론 시스템인 전문가 시스템을 이용하여 배치할 형상이나 배치될 소재 경계 형상 등에 대한 제약 없이 네스팅 문제를 해결하고자 하며, 제안된 방법을 이용하여 각각 다른 특성을 갖는 네스팅 문제에 적용하여 그 적용 가능성을 예시하고자 한다.

제안 방법

예를 들어 8 개의 부재를 배치할 때 약 26억가지 이상의 경우의 수가 발생한다. 따라서 기존의 연구들에서는 큰 부재부터 한 쪽 끝부터 순차적으로 연속 배치하는 방식을 사용하였으나 본 연구에서는 각 부재를 배치할 때 이전 부재에 이어서 배치하는 것이 아니라 제약 없이 전 평판을 활용하여 배치를 한다.
Initialize 규칙에서는 각 부재를 먼저 크기 순서로 정렬한 후 이를 Lay-tile-list에 저장한다. 또한 각각의 부재에 대하여 8 가지 자세를 생성하며 적용 분야에 따라 자세의 가짓수를 조정한다. 예를 들어 의복제조 분야와 같아 소재의 앞 뒷면을 구별해야 하는 경우 거울 이미지는 고려할 필요가 없고, 조선 블록 생산 시 소요되는 보강재류와 같이 긴 소재에 폭이 같은 부재들을 배치하는 경우 90º,270º의 회전 형상 및 그에대한 미러(Mirror) 형상은 고려할 필요가 없다.
하나의 부재는 회전각에 따라 무한한 가짓수의 자세를 가질 수 있으나 본 연구에서는 0º,90º,180º,270º회전 형상, 그리고 각각에 대한 미러(Mirror) 이미지 등 최대 총 8 가지 자매 형상을 고려한다.

이론/모형

문제에 대한 사전 정보가 없을 때 문제를 해결하는 일반적인 탐색 트리는 크게 깊이 방향을 먼저 탐색하는 깊이우선(Depth-first) 탐색 트리와 같은 깊이에서 가능한 경우의 수를 먼저 모두 탐색하는 폭우선(Breadth-first) 탐색 트리로 나눌 수 있다. 문제의 해를 찾는 탐색 방향에 관한 정보가 있을 때는 각 노드에서 다음 탐색할 노드들에 대하여 해에 근접한 정도와 관련된 평가함수(Evaluation function)를 계산하여 그 값이 큰 노드부터 탐색하는 휴리스틱(Heuristic) 탐색 방법을 사용한다.
또한 조선소 야적장에서의 블록 배치 문제도 네스팅 문제로 볼 수 있다. 이러한 네스팅 문제는 각 형상별로 자세 및 배치될 위치 등을 찾아야 하는데 NP-complete(Non determimistric polynomial complete) 문제로서(Bennell and Oliveira, 2008) 알고리즘적인 방법으로 최적해를 찾을 수 없어 통상적으로 휴리스틱 방법을 이용한다. 상업용 CAD 시스템들에서 사용하고 있는 방법 또한 휴리스틱 방법에 기반을 두고 있는데(한국찬과 나석주, 1994), 부재들 간의 순서를 정한 후 배치할 부재들을 볼록 다각형으로 단순화하여 기존에 배치된 부재에 NFP(Nofit polygon) 알고리즘(Burke et al.

성능/효과

퍼즐문제, 일반 네스팅 문제, 그리고 조선 강재류 네스팅 예제에 적용하여 그 적용 가능성을 보였으며, 각 문제별로 특성을 고려하여 문제를 효과적으로 해결할 수 있음을 설명하였다. 또한 형상들을 배치할 평판 소재의 형상이 사각 판넬이 아닐 경우에도 가상의 사각 판넬을 경계로 실제 경계 형상부분까지 이미 다른 형상이 배치되어 있는 상태로 처리하면 되므로 평판 소재의 형상도 문제가 되지 않음을 예제를 통하여 보였다. 강재 네스팅 문제 등에서 고려해야 할 형상 간 공구 경로 확보 문제는 각 형상에 공구경로 폭에 해당하는 Offset을 추가하는 방법으로 해결될 수 있다.
본 연구에서 개발한 네스팅 전문가 시스템은 평가함수를 활용한 휴리스틱 탐색을 통하여 해를 비교적 짧은 시간(예제들의 경우 수천에서 수만개 이내의 노드 탐색)에 제시할 수 있었다. 퍼즐문제, 일반 네스팅 문제, 그리고 조선 강재류 네스팅 예제에 적용하여 그 적용 가능성을 보였으며, 각 문제별로 특성을 고려하여 문제를 효과적으로 해결할 수 있음을 설명하였다.
일반적인 네스팅 문제는 NP-complete 문제로서 형상 개수가 늘어날수록, 표현의 정밀도를 높이기 위하여 픽셀의 갯수가 늘어날수록 최적해를 구하는 것은 거의 불가능하다. 본 연구에서 개발한 시스템도 평가함수를 활용한 휴리스틱 탐색 기법으로 탐색 시간을 줄였으나 형상의 개수가 늘어나거나 형상 표현 정밀도를 높이기 위하여 픽셀 수를 늘릴 경우 탐색 시간이 길어진다. 따라서 이러한 경우에는 픽셀 수를 줄여 해상도를 낮추거나 형상들을 일정 단위로 묶어 그룹별로 네스팅 한 후 그룹 간 네스팅하는 방법 등을 강구할 수 있을 것이다.
본 연구에서 개발한 네스팅 전문가 시스템은 평가함수를 활용한 휴리스틱 탐색을 통하여 해를 비교적 짧은 시간(예제들의 경우 수천에서 수만개 이내의 노드 탐색)에 제시할 수 있었다. 퍼즐문제, 일반 네스팅 문제, 그리고 조선 강재류 네스팅 예제에 적용하여 그 적용 가능성을 보였으며, 각 문제별로 특성을 고려하여 문제를 효과적으로 해결할 수 있음을 설명하였다. 또한 형상들을 배치할 평판 소재의 형상이 사각 판넬이 아닐 경우에도 가상의 사각 판넬을 경계로 실제 경계 형상부분까지 이미 다른 형상이 배치되어 있는 상태로 처리하면 되므로 평판 소재의 형상도 문제가 되지 않음을 예제를 통하여 보였다.

후속연구

전문가 시스템은 일반 프로그램과 달리 시스템에 대한 전체적 수정 없이 새로운 규칙을 지식베이스에 추가하는 방법으로 시스템 성능을 쉽게 개선할 수 있으며 따라서 본 시스템도 경험 지식 등에 의한 새로운 규칙을 추가하므로써 지속적 성능 개선이 가능할 것으로 기대된다. 또한, 본 연구에서 사용한 픽셀을 이용한 형상표현 방법을 이용할 경우 상업용 CAD 시스템과 쉽게 연계할 수 있으며, 오목한 형상이나 구멍이 있는 형상들을 배치하는데 도형의 근사형상을 이용한 방법과 달리 볼록 형상으로 근사화해야 하는 등의 제약이 없다.

질의응답

핵심어	질문	논문에서 추출한 답변
	네스팅(Nesting)이란 무엇인가?	네스팅(Nesting)은 다양한 모양의 여러 형상들을 평판 소재에서 잘라내거나 평면 상에 배치할 때 낭비되는 소재 또는 공간이 최소화 되도록 형상들을 배치하는 문제라 정의할 수 있다. 조선소의 강재절단, 자동차 및 기계부품 공장 등에서 블랭킹 공정, 의복 공장, 구두공장, 가구공장 등에서의 소재절단 공정에서 형상들을 배치하는 문제는 대표적인 네스팅 문제로서 가능한 한 공간적으로 빼곡히 배치하면 버려지는 부분을 작게 함으로써 재료비를 절약할 수 있다.
	대표적인 네스팅 문제로는 무엇이 있는가?	네스팅(Nesting)은 다양한 모양의 여러 형상들을 평판 소재에서 잘라내거나 평면 상에 배치할 때 낭비되는 소재 또는 공간이 최소화 되도록 형상들을 배치하는 문제라 정의할 수 있다. 조선소의 강재절단, 자동차 및 기계부품 공장 등에서 블랭킹 공정, 의복 공장, 구두공장, 가구공장 등에서의 소재절단 공정에서 형상들을 배치하는 문제는 대표적인 네스팅 문제로서 가능한 한 공간적으로 빼곡히 배치하면 버려지는 부분을 작게 함으로써 재료비를 절약할 수 있다. 또한 조선소 야적장에서의 블록 배치 문제도 네스팅 문제로 볼 수 있다.
	픽셀로 형상을 표현하는 방법은 간단하고 형상간 중첩여부를 쉽게 판단할 수 있는 반면 단점은 무엇인가?	네스팅 기법은 형상표현 방법에 따라 픽셀로 형상을 표현하는 방법과 형상을 근사화한 다각형으로 표현하는 방법으로 나눌 수 있다. 픽셀 형태를 이용할 경우 표현이 간단하고 형상간 중첩여부를 쉽게 판단할 수 있는 반면, 정밀한 형상 표현을 위해서는 많은 양의 메모리와 계산시간이 소요된다. 반면 다각형으로 형상을 표현하는 경우 다각형의 경계를 정의하는 점과 선들의 정보만을 처리하게 되므로 상대적으로 적은 메모리를 이용하나, 형상간 중첩 여부를 판단하는 알고리즘이 복잡해진다.

참고문헌 (9)

이철수, 박광렬 (1996). "선박용 플랫바의 자동네스팅 및 가스/플라즈마에 의한 NC 절단", 산업공학, 제9권, 제3호, pp 283-297.

원문보기 상세보기
한국찬, 나석주 (1994). "레이저 절단공정에서 절단부재의 최적 배치를 위한 네스팅 알고리즘", 대한용접학회지, 제12권, 제2호, pp 11-19.

원문보기 상세보기
한창봉, 박제웅 (1999). "파라메트릭 매크로를 이용한 부재생성 및 네스팅에 관한 연구", 한국해양공학회지, 제13권, 제2호, pp 176-185.

원문보기 상세보기
Babu, A.R. and Babu, N.R. (2001). "A Generic Approach for Nesting of 2-D Parts in 2-D Sheets using Genetic and Heuristic Algorithms", Computer-Aided Design, Vol 33, pp 879-891.
Bennell, J.A. and Oliveira, J.F. (2008). "The Geometry of Nesting Problems: A Tutorial", European Journal of Operational Research, Vol 184, pp 397-415.

상세보기
Burke, E.K., Hellier, R.S.R., Kendall, G. and Whitwell, G. (2007). "Complete and Robust No-fit Polygon Generation for the Irregular Stock Cutting Problem", European Journal of Operational Research, Vol 179, pp 27-49.

상세보기
Lee, W.-C., Ma, H. and Cheng, B.-W. (2008). "A Heuristic for Nesting Problems of Irregular Shapes", Computer-Aided Design, Vol 40, pp 625-633.

상세보기
Tay, F.E., H. Chong, T.Y. and Lee, F.C. (2002). "Pattern Nesting on Irregular-shaped Stock using Genetic Algorithms", Engineering Applications of Artificial Intelligence, Vol 15, pp 551-558.

상세보기
Weng, W.C. and Kuo, H.C. (2011). "Irregular Stock Cutting System Based on AutoCAD", Advances in Engineering Software, Vol 42, pp 634-643.

상세보기

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

휴리스틱 탐색 기법을 이용한 네스팅 전문가 시스템
Nesting Expert System using Heuristic Search 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약
AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

휴리스틱 탐색 기법을 이용한 네스팅 전문가 시스템 Nesting Expert System using Heuristic Search 원문보기

Abstract ▼ AI-Helper

주제어

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

이론/모형

성능/효과

후속연구

질의응답

참고문헌 (9)

이 논문을 인용한 문헌

저자의 다른 논문 :

신동목 (12)

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

휴리스틱 탐색 기법을 이용한 네스팅 전문가 시스템
Nesting Expert System using Heuristic Search 원문보기

AI 본문요약
AI-Helper