Earticle

친환경 연료의 필요성이 대두되면서 화석연료의 사용이 줄어들고 있다. 이에 따라 해양경찰은 국가기조에 맞게 최근 해양오염 방제선을 LNG 선박으로 건조하는 등 연료 시스템 전환에 힘쓰고 있다. 그러나 기존연료대비 암모니아, 메탄올, 수소, LNG와 같은 인화성 혹은 독성이 높은 연료를 선박 연료로 사용할 경우, 누출 사고 에 대비한 방안을 마련해야 한다. 이에 따라 세계적으로 친환경 연료 사용과 첨단 해양 모빌리티 기술 개발 및 안전에 관한 연구가 활발히 진행되고 있다. 따라서 기 존 MDO 연료를 사용하는 실습선의 연료를 암모니아 연료로 가정하여 피해범위를 예측하였다. 이와 더불어 AI 딥러닝 기반의 전처리 시스템 모듈을 구축 및 경로 탐 색 알고리즘을 활용해 인원수, 통로폭, 선체 기울기에 따른 최적 대피 경로를 도출하 였다. 가스 누출에 따른 피난 시, 딥러닝을 통해 구역별 최대 인구밀도가 5.4 per/㎡ 에서 일반적인 경로 탐색 방식과 비교한 결과 2.6 per/㎡로 개선 됨을 확인하였다. 이에 따라 전체 피난 시간이 1,030초에서 248초로 감소되었으며 기존 대비 예상 사망자 수가 67명 줄어 생존율이 35% 향상되었다. 따라서 본 연구에서 제안한 프로그램은 선박재난 상황에서 최적의 대피 경로를 도출하여 승객 및 승조원의 안전을 확보하는 의사결정 지원 기초 자료로 활용될 수 있을 것으로 보인다.

As the need for eco-friendly fuel arises, the use of fossil fuels is decreasing. Accordingly, the korea coast guard are striving to convert the fuel system by building the marine pollution control ship with LNG ships. However, when highly flammable fuels such as LNG and hydrogen are used as ship fuel, it is necessary to prepare a plan for a leakage accident. Against this background, research on the use of eco-friendly fuels and the development and safety of advanced marine mobility technologies is being actively conducted. Therefore, in this study, a post-processing system module based on a convolutional neural network was constructed, and the optimal evacuation route according to the number of people, passage width, and hull trim was derived using a deep learning model and path search algorithm based on a deep neural network. As a result of comparing it with the classical pathfinding method under the assumed conditions, the maximum population density by area was improved from 5.4 per/㎡ to 2.6 per/㎡ through deep learning. In addition, the total evacuation time decreased from 1,030 seconds to 248 seconds, and the estimated number of deaths decreased by 67, improving the survival rate by 35%. Therefore, the program developed in this study is expected to be used as decision support data to secure the safety of passengers and crew by deriving the optimal evacuation route in a disaster situation.

Pathfinding for pedestrians provided by various navigation programs is based on a shortest path search algorithm. There is no big difference in their guide results, which makes the path quality more important. Multiple criteria should be included in the search cost to calculate the path quality, which is called a multi-criteria pathfinding. In this paper we propose a user adaptive pathfinding algorithm in which the cost function for a multi-criteria pathfinding is defined as a weighted sum of multiple criteria and the weights are learned automatically by Perceptron learning. Weight learning is implemented in two ways: short-term weight learning that reflects weight changes in real time as the user moves and long-term weight learning that updates the weights by the average value of the entire path after completing the movement. We use the weight update method with momentum for long-term weight learning, so that learning speed is improved and the learned weight can be stabilized. The proposed method is implemented as an app and is applied to various movement situations. The results show that customized pathfinding based on user preference can be obtained.

Pipe routing during the design process of a ship depends on the design experience or knowledge of experts. In this study, an expert system that can systematize expert knowledge was constructed to enhance the design of a ship's pipe routing, which relies on experts. In addition, a method for pipe routing using a pathfinding algorithm was proposed. An arrangement template model (a type of data structure for pipe routing) and an arrangement evaluation model (a type of expert system) were proposed to systematically concretize and computerize expert knowledge. To review several alternatives for pipe routing in a short time and derive an optimal alternative, an optimization technique was combined with an expert system, and the optimization problem was mathematically formulated. That is, the design alternatives for pipe routing were evaluated using the arrangement evaluation model, and the results were used as one of the objective functions of the optimization problem for optimal pipe routing. To verify the proposed method, examples were selected, pipe routing was performed on the examples, and the results were compared with those of the manual design. As a result, an improved pipe routing could be obtained using the proposed method.

휴리스틱 기반의 유전 알고리즘 경로 탐색(H-GAP)은 노드, 에지 정보를 필요로 하지 않기 때문에 기존 경로 탐색 알고리즘의 단점을 보완하고 빠른 속도로 경로 탐색을 수행할 수 있다. 하지만 H-GAP를 이용해 탐색한 경로는 비 노드 기반이기 때문에 불필요한 경로 정보가 포함되어 탐색된 경로가 최적의 경로가 아닐 때도 있다. 본 논문에서는 H-GAP를 이용해 탐색한 경로를 최적화하는 알고리즘을 제안한다. 제안하는 알고리즘은 H-GAP의 경로 탐색이 완료된 후 광선 추적 알고리즘을 이용해 불필요한 경로 정보를 제거하여 경로를 최적화한다.

Heuristic based Genetic Algorithm Pathfinding(H-GAP), a method without the need for node and edge information, can compensate the disadvantages of existing pathfinding algorithm, and perform the path search at high speed. However, because the pathfinding by H-GAP is non-node-based, it may not be an optimal path when it includes unnecessary path information. In this paper, we propose an algorithm to optimize the search path using H-GAP. The proposed algorithm optimizes the path by removing unnecessary path information through ray-tracing algorithm after the H-GAP path search is completed.

휴리스틱 기반의 유전 알고리즘 경로 탐색(H-GAP)은 노드, 에지 정보를 필요로 하지 않기 때문에 기존 경로 탐색 알고리즘의 단점을 보완하고 빠른 속도로 경로 탐색을 수행할 수 있다. 하지만 H-GAP를 이용해 탐색한 경로는 비 노드 기반이기 때문에 불필요한 경로 정보가 포함되어 탐색된 경로가 최적의 경로가 아닐 때도 있다. 본 논문에서는 H-GAP를 이용해 탐색한 경로를 최적화하는 알고리즘을 제안한다. 제안하는 알고리즘은 H-GAP의 경로 탐색이 완료된 후 광선 추적 알고리즘을 이용해 불필요한 경로 정보를 제거하여 경로를 최적화한다.

Heuristic based Genetic Algorithm Pathfinding(H-GAP), a method without the need for node and edge information, can compensate the disadvantages of existing pathfinding algorithm, and perform the path search at high speed. However, because the pathfinding by H-GAP is non-node-based, it may not be an optimal path when it includes unnecessary path information. In this paper, we propose an algorithm to optimize the search path using H-GAP. The proposed algorithm optimizes the path by removing unnecessary path information through ray-tracing algorithm after the H-GAP path search is completed.

국제해사기구는 해상에서의 대규모 인명사고를 줄이기 위하여 승객 안전 기준을 보완해왔다. 이에 따라 본 연구에서는 좁은 통로와 많은 승선인원이 상주하는 실습선을 대상으로 선박 환경에서 대피 시뮬레이션 시 유리한 경로 탐색 알고리즘을 선정하기 위한 연구를 수행하였다. 비교 대상으로 선정한 알고리즘은 Dijkstra, Theta^*, Fast Marching Method이며, 보행자간 상호작용 및 보행자와 벽면으로 인한 혼잡도 기반의 경로 탐색을 시뮬레이션하였다. 주·야간 시나리오에서 대피 시간, 혼잡도 분포, 위험 점유면적 기준으로 성능을 분석한 결과, 대피 시간은 세가지 알고리즘의 결과에서 약 0.1초 내외로 유사하게 나타났으나 Theta^*가 시나리오에 따른 성능 변동성이 가장 낮았으며, 혼잡도 분포 및 위험 점유면적 또한 타 알고리즘 대비 최대 23%의 혼잡도 저감 능력을 보이며 가장 높은 성능을 나타냈다. 이러한 결과는 Line-of-Sight 특성을 갖는 Theta^* 알고리즘이 좁은 통로와 높은 인구 혼잡도 상황에서 대안 경로를 형성하여 혼잡을 완화한 것이 원인으로 판단된다. 본 연구의 결과는 선박 설계 및 피난안전성 평가 시 경로 탐색 알고리즘을 선정하는데 참고자료로서 활용될 수 있을 것으로 보인다.

The International Maritime Organization has been supplementing passenger safety standards to minimize the number of large-scale human accidents at sea. Accordingly, this study aims to select an advantageous route search algorithm when simulating evacuation in a ship environment for training ships with narrow passages and a large number of onboard passengers. The algorithms selected for comparison include Dijkstra, Theta^*, and Fast Marching Method, which simulate pedestrian interaction and congestion-based route search by accounting for pedestrian and wall surfaces. As a result of analyzing the performance based on the evacuation time, congestion distribution, and risk occupancy area in the day and night scenarios, the evacuation time was similar in the results of the three algorithms, but Theta^* showed the lowest performance volatility, and the congestion distribution and risk occupancy area also showed the highest performance, with the ability to reduce congestion by up to 23% compared to other algorithms. This result is judged to be due to the fact that the Theta^* algorithm with line-of-Sight characteristics alleviating congestion by forming an alternative route in narrow passages and high population congestion scenarios. The finding in this study can be used as a reference for selecting route search algorithms when evaluating ship design and evacuation safety.

게임 플랫폼의 고도화와 게임 구현 기술의 발전을 통해 이루어지고 있는 개발 환경의 효율성 제고를 통해 이전에 게임의 구현 자체에 소요하는 시간을 게임 콘텐츠의 질적 향상을 위해 투입할 수 있는 여건이 형성되고 있다. 본 논문은 게임에서 등장하는 NPC가 보다 사실적인 추론을 통해 플레이어를 추적하도록 지정하는 알고리즘을 고수준의 카테고리로 구분하여 구현하여, 개발 과정에서의 NPC 구현에 효율성을 제고하는 기법을 제안한다. NPC가 플레이를 추적하는 스토리를 기반으로 하는 게임에서 NPC가 플레이어의 위치에 도달하기 위한 길찾기 알고리즘은 필수적이다. 일반적으로 사용되는 최단 거리 길찾기 알고리즘인 다익스트라(Dijkstra)의 경우, 효율적이지만 플레이어가 NPC의 경로를 예측 가능할 수 있기에 게임의 재미 향상에 걸림돌이 되는 단점이 있다. 본 논문에서는 최단 거리 길찾기를 구현하면서 다양한 게임 스토리 상의 설정으로 지정할 수 있는 다양한 방법론을 연구하였으며, 이를 구현하기 위한 고수준 길찾기에 대한 방법을 제시한다.

This paper describes the solution method of Team AIRLAB used to participate in the League of Robot Runners Competition which tackles the problem of Lifelong Multi-agent Pathfinding (MAPF). In lifelong MAPF, multiple agents are tasked to navigate to their respective goal locations where new goals are consecutively revealed once they reach initial goals. The agents need to avoid collisions and deadlock situations while they navigate to perform tasks. Our method consists of (i) Puzzle Heuristics, (ii) MAPF-LNS2, and (iii) RHCR. The Puzzle Heuristics is our own algorithm that generates a compact heuristic table contributing to reduce memory consumption and computation time. MAPF-LNS2 and RHCR are state-of-the-art algorithms for MAPF. By combining these three algorithms, our method can improve the efficiency of paths for all agents significantly.

중소기업 현장에서 운용되고 있는 재고, 제품 관리 시스템을 기반으로, 숙련공의 경험적 지식(암묵지)를 형식지화 할 수 있는 방법을 제시하기 위해 기존 자료를 기반으로 하는 데이터 수집 및 가공 설계 파이프라인을 제시. 또한 해당 데이터를 기반으로 GA, AI기술 적용을 도모하여 기존의 업무지원시스템(Warehouse Management System, WMS / Manufacturing Execution System, MES)에서 제시할 수 없었던 "업무 지식의 자동화된 승계"의 기초를 마련하는 방법을 제시하고자 한다.

본 논문은 다양한 네트워크를 편리하게 분석할 수 있는 실용적인 유전 알고리즘 기반 경로탐색 시스템인 GAPS를 제안하고자 한다. 이러한 목적을 위해 GAPS는 네트워크 모델링을 위한 직관적인 그래픽 사용자 인터페이스와 모델링 및 탐색 과정에서 발생하는 데이터들을 관리하기 위한 데이터베이스 관리 시스템, 다양한 네트워크를 분석하기 위해 개발된 간단한 유전 알고리즘을 결합하여 개발되었다. 특히, 기존의 유전 알고리즘들이 단락이 많고 두 개 노드 간 실행가능 경로 수가 많지 않은 네트워크를 분석하는데 적합하지 않았던 반면, GAPS는 실행가능 경로와 실행불가능 경로를 모두 적절히 평가할 수 있는 적합도 함수를 사용하는 유전 알고리즘에 기반하고 있어 해 집단의 다양성을 유지하면서 다양한 네트워크들을 분석할 수 있다. 실험결과, GAPS를 통해 단락이 많은 네트워크와 단락이 적은 네트워크를 모두 편리하게 분석할 수 있다는 점과, GAPS가 기존의 경로탐색문제를 위한 유전 알고리즘들과 대비되는 장점을 갖고 있음을 확인할 수 있었다.

This paper proposes GAPS, a practical genetic algorithm based pathfinding system for conveniently analyzing various networks. To this end, the GAPS is developed through integration of the intuitive graphic user interface for network modeling, the database management system for managing the data generated in modeling and exploring procedures, and a simple genetic algorithm for analyzing a wide range of networks. Especially, previous genetic algorithms are not appropriate for analyzing the networks with many dead-ends where there are few feasible paths between the given two nodes, however, GAPS is based on the genetic algorithm with the fitness function appropriate for evaluating both feasible and infeasible paths, which enables GAPS to analyze a wide range of networks while maintaining the diversity of the population. The experiment results reveal that GAPS can be used to analyze both networks with many dead-ends and networks with few dead-ends conveniently, and GAPS has several advantages over the previous genetic algorithms for pathfinding problems.

게임에서 캐릭터가 현재 위치에서 목적지까지 경로를 탐색하는 것은 매우 중요하다. 특히, 오브젝트나 벽 등의 장애물들이 배치된 복잡한 게임 맵에서는 이러한 장애물을 회피하면서 가능한 최단 경로를 찾아 이동해야 한다. 본 논문에서는 복잡한 게임 맵 상에서 캐릭터가 목적지까지 최단 경로를 탐색하는 방법으로 유전자 알고리즘을 적용하는 방법을 제안한다. 유전자 알고리즘은 모집단(Population)을 구성하는 염색체의 인코딩 및 디코딩, 진화를 위한 연산자인 교차연산(Crossover)과 돌연변이연산(Mutation), 그리고 염색체를 평가하는 목적함수로 구성된다. 본 논문에서는 염색체 구성을 시작 노드에서 목적지 노드까지의 전체 노드로 구성하기 보다는 캐릭터의 현재노드에서 이동할 수 있는 8방향만으로 구성하여 염색체의 크기를 줄였고, 이를 통해 염색체의 인코딩과 디코딩 연산 시간을 줄일 수 있었다.

진화 알고리즘과 인공신경망은 생물학에서 비롯되어 컴퓨터과학 분야에서 응용되고 있는 문제해결 방법이다. 본 연구는 게임 환경에서 크기를 자율적으로 설정하여 생성할 수 있는 미로를 구성하고, 주어진 미로의 시작점으로부터 목적지까지 유전 알고리즘과 인공신경망을 이용하여 경로탐색을 하는 것에 대한 연구이다. 자동 생성된 미로가 특정 크기 이상으로 커지게 되면, 진화 알고리즘은 무작위적인 값에 의해서 결정되는 것으로 수렴한다는 결론을 얻었고, 인공신경망을 이용한 결과는 진화알고리즘 보다 미로의 경로탐색 문제해결에 적합한 결과를 보여주었다. 또한 어떤 방향이 최적경로인지 아닌지를 미리 알 수 있는 특수한 조건에서는 각 유전인자를 최적값인지 아닌지 표현하는 방법으로 효율적인 진화 알고리즘을 사용할 수 있다는 것을 제안하였다.

진화 알고리즘과 인공신경망은 생물학에서 비롯되어 컴퓨터과학 분야에서 응용되고 있는 문제해결 방법이다. 본 연구는 게임 환경에서 크기를 자율적으로 설정하여 생성할 수 있는 미로를 구성하고, 주어진 미로의 시작점으로부터 목적지까지 유전 알고리즘과 인공신경망을 이용하여 경로탐색을 하는 것에 대한 연구이다. 자동 생성된 미로가 특정 크기 이상으로 커지게 되면, 진화 알고리즘은 무작위적인 값에 의해서 결정되는 것으로 수렴한다는 결론을 얻었고, 인공신경망을 이용한 결과는 진화알고리즘 보다 미로의 경로탐색 문제해결에 적합한 결과를 보여주었다. 또한 어떤 방향이 최적경로인지 아닌지를 미리 알 수 있는 특수한 조건에서는 각 유전인자를 최적값인지 아닌지 표현하는 방법으로 효율적인 진화 알고리즘을 사용할 수 있다는 것을 제안하였다.