Structural topology optimization using genetic algorithms with Dijkstra's shortest path algorithms : 유전알고리즘과 다익스트라 최단거리 알고리즘을 이용한 구조 위상 최적화

김용겸 세종대학교 대학원 2017 국내석사

In the present study, a strategy is proposed to define the optimized topology based on the path representation using Dijkstra's shortest path algorithms and by using genetic algorithms (GA) which is perceived as a robust and powerful stochastic global search method. In a given two-dimensional design domain, a valid topology is represented by a connected path constructed along the strain energy. This path consists of a set of each finite element interconnected with shortest path. This algorigthm determines the shortest path between starting point and the destination point using a path consisting of each element. A each loading part of the structure, there can be at least one path to transfer the external loading to the support part. The optimized structure topologies can be completely connected to bear external loading, to this end, the shortest path in the topology is searched to be connected continuously while satisfying the given condition (as called weight) in design domain. The resulting topology can be guaranteed continuous connection requirements, and the complexity of computation depends primarily on the number and distribution of vertices in the design domain. Application of this path representation into the structural optimization problems by using the GA and to derive the results through numerical experiments. This path representation is suggested to be computationally efficient and physically meaningful in the framework of a topology optimization design using GA, and the advantages of the proposed strategy include guaranteed connectivity of the structure, basic of results topology complexity and probabilistic global optimization approach. The numerical results are also better than the existing cell-based method in geometry connectivity and convergence speed, and improved path representions can be seen. 본 연구에서는 다익스트라 최단 경로 알고리즘을 사용하며 유용하고 강력한 확률 적 글로벌 검색 방법으로 인식되는 유전 알고리즘 (GA)을 사용하여 경로 표현을 기반으로 최적화 된 토폴로지를 정의하는 전략을 제안한다. 주어진 2차원 설계 영역에서 유효한 토폴로지는 변형 에너지를 따라 구성된 연결 경로로 표현 된다. 또한 경로 표현형 유전자알고리즘은 적절하게 설정된 GA 연산을 사용하여 구조적 위상 최적화 문제에 적용된다. 이 알고리즘은 각 요소로 구성된 경로를 사용하여 출발점과 목지 지점 사이의 최단 경로를 결정 하게 된다. 최적화 된 구조 위상은 외부 로딩을 위해 완벽하게 연결될 수 있으며, 이를 위해 위상의 최단 경로를 검색하여 디자인 도메인에서 주어진 조건을 만족시키면서 연속적으로 연결되도록 한다. 최단 경로를 결정한 후, 최단 경로로 구성된 위상을 사용하여 외부하중에 대한 변형 에너지를 계산하여 위상의 최적화 문제에 대해 유전알고리즘의 지정된 조건이 충족 될 때까지 반복 프로세스가 수행되게 된다. 이 경로 표현은 유전알고리즘을 사용하는 위상 최적화 설계에서 계산적으로 효율적이고 물리적으로 의미가 있다고 제안되며 또한 구조물의 연결성이 보장된다.

다익스트라 알고리즘을 이용한 화재 피난 방향 안내 시스템의 설계 및 구현

강윤구 충북대학교 2022 국내석사

본 연구는 DHT22 온도 센서를 활용하여 화재 시 발화 지점을 추정하고, dijkstra 알고리즘을 활용한 최단거리 대피 경로 생성 및 피난방향 안내 시스템을 설계 및 구현한다. 건물에서 화재가 발생했을 경우, 대피자는 화재 발생에 따른 건물의 유도등 또는 소리, 건물 구조의 지각 능력으로 최종 탈출구를 스스로 판단해야 한다. 하지만 이 경우 건물을 탈출하는 과정에서 대피자는 탈출구로의 최단 거리가 아닌 화재가 발생한 위치의 정확한 인지 없이 가장 가까운 통로 또는 층계로 이동하려고 하여 화재가 발생한 건물 내에서 지체하는 경우가 발생하게 된다. 탈출을 위해서는 화재가 발생한 초기에 탈출을 시도하는 것이 가장 바람직하며, 화재의 발생 상태가 진전되더라도 최적의 경로로 유도하게 된다면 많은 대피자가 탈출에 성공할 수 있다. 따라서 본 연구에서는 DHT22 온도 센서를 통해 정확한 발화점을 파악한 후, 안전한 최단 탈출 경로를 대피자에게 정확하게 안내함으로써 많은 대피자가 혼란을 피해 안전하게 탈출에 성공할 수 있도록 하였다. 종래의 화재 경로를 안내하기 위한 유도등은 불길 또는 연기에 의해 그 기능을 잃고, 대피자는 탈출구를 찾는데 더욱 어려워져 옥외의 탈출 시간이 지연되는 문제가 발생하였으나, 이번 연구에서는 대피자의 무릎 높이에 안내 표시장치를 설치하여 시인성이 향상 시켰다. 해당 시스템을 검증하기 위하여 실제 빌딩에 모의 피난방향 안내 시스템을 설치하고, 유효성을 검증하였다. This study estimates the firing point in case of a fire using the DHT22 temperature sensor and designs and implements the shortest-distance evacuation route generation and evacuation direction guidance system using the Dijkstra algorithm. In the event of a fire in a building, the evacuees shall determine the final escape by themselves based on the building's guiding light or sound, and the perceptual ability of the structure of the building. However, in this case, in the process of escaping the building, evacuees may delay in the building where the fire broke out by trying to move to the nearest passage or stairs without accurate recognition of the location of the fire. In order to escape, it is most desirable to try to escape in the early stages of a fire, and even if the state of the fire progresses, many evacuees can succeed in escaping if it is guided to the optimal path. Therefore, in this study, the exact ignition point was identified through the DHT22 temperature sensor, and the safe shortest escape route was accurately guided to the evacuees so that many evacuees could safely escape from confusion. The conventional guide lamp for guiding the fire path loses its function due to fire or smoke, and it is more difficult for an evacuee to find an exit, and thus the outdoor escape time is delayed, but in this study, a guide display is installed at the knee height of the evacuee. In order to verify the system, a simulated evacuation direction guidance system was installed in an actual building, and the validity was verified.

레거시 정보를 이용한 최단경로의 재구성 및 최적 경로 구성 알고리즘에 관한 연구

김주백 鮮文大學校 2008 국내박사

Abstract Ju-Baeg Kim Department of Computer and Information Science Graduate School Sun Moon University Adviser: Professor Jung-Ho Park Various information retrieval methods are currently being used on the Internet. For example, the shortest-path system obtains information from a shortest-path database (DB) that is constructed in advance using shortest-path algorithms. However, these systems are unsuitable in contexts such as train movement; if an accident disrupts the tree between any two stations, the shortest-path DB does not apply. Such cases require the problem to be analyzed from the very beginning using shortest-path algorithms. This paper refers to these kinds of problems as the class of 'reconfiguring problems' and propose methods to handle reconfiguring problems efficiently. This paper develops algorithms for processing reconfiguring problems; specifically, it discusses the reconfiguring problem related to a breadth-first search tree, the shortest path for a weighted graph, and a minimum-weighted spanning tree. Of retrieval methods used to obtain shortest-path information for a non-weighted graph, a breadth-first search algorithm is the most efficient. Dijkstra’s algorithm is the most efficient retrieval method for a weighted graph. Existing systems use breadth-first or Dijkstra’s algorithms to find shortest-path information from the shortest-path database (DB), which is constructed in advance by breadth-first or Dijsktra’s algorithms. However, these methods are not applicable to systems such as railroads in the real world. An accident, such as an electrical malfunction, can disrupt the path between any two stations, making the existing shortest-path DB unusable. These kinds of issues must be resolved to handle such problems. When an accident occurs in a train system, the original graph changes and the new graph contains the shortest path of the original graph, i.e. the graph before the accident. This shortest path is the old solution, and the new graph cannot use this old solution intact. In this paper, we propose an algorithm to process the shortest path efficiently using the old solution, referred to as ‘legacy data.’ Our algorithm does not reconstruct the graph’s entire path after the change from scratch; by using legacy data, we omit the unaffected part of the shortest path and reconstruct only the part that was affected by the change. Consider the case of the shortest path in a subway. The transfer process can greatly affect the shortest-path search. For example, pregnant women or elderly people need more time during subway transfer. Previous methods, such as Dijkstra’s algorithm, might offer unavailable shortest-path information because they do not consider the condition of transit passengers, e.g., passenger health. To find shortest-path information efficiently while taking into account the condition of transit passengers, we suggest a variable weighted graph that uses information about the passengers’ condition and the original weighted graph. Information from the original weighted graph consists of the transfer time between any two stations and the transfer time at any station. In addition, we propose a method that offers available shortest-path information using the variable weighted graph. This paper develops a system that provides this shortest-path information within the context of the condition of transit passengers. When taking the subway, users encounter transfer stations. Depending on the circumstances, no single transfer station is fastest. For example, pregnant women or old people may need more transfer time, while a young student may not. A method such as Dijkstra’s algorithm might offer unavailable shortest-path information because it does not consider that transfer time may vary among passengers. Therefore, this paper proposes a new graph: a variable weighted graph, which considers transfer time according to a passenger’s condition. The variable weighted graph is an extension of a weighted graph. This paper explains the variable weighted graph and our method for obtaining available shortest-path information using a variable weighted graph. 인터넷상에서의 정보검색을 위한 다양한 방법이 고안되어 이용되고 있는데, 가령, 최단경로 정보검색에 있어서는 다익스트라 알고리즘을 이용하여 정보서비스가 이루어지고 있다. 최단경로탐색은 네트워크 분석에서 기본적인 기능으로서, 주어진 시작노드에서 목표노드까지의 최소비용을 갖는 경로를 찾아준다. 여기서 네트워크란 노드(node)와 두 노드를 연결하는 에지(edge)들의 집합으로서 각 에지에 비용(cost)이 부가되어진다. 기존 서비스의 경우, 출발지와 목적지가 주어지면 다익스트라 알고리즘 등을 이용하여 사전에 구축해 둔 최단경로 데이터베이스로부터 경로정보를 제공하는데, 가령, 어느 두 역사의 선로에 이상이 있을 경우에는 최단경로 데이터베이스를 이용할 수 없으므로 최단경로를 다시 구축해야 한다. 이러한 문제를 본 논문에서는 재구성문제(reconfiguring problem)이라고 정의하기로 한다. 최단경로 재구성문제를 해결하기 위한 가장 단순한 방법은 변경된 그래프에 대해 처음부터 다익스트라 알고리즘 등을 적용하여 최단경로를 구하는 방법을 들 수 있다. 본 논문에서는 최단경로 재구성문제를 보다 효율적으로 해결하기 위해서, 기존 그래프에 대한 최단경로 정보를 이용하는 효율적인 알고리즘을 제안한다. 그리고, 일반적인 최단경로 제공 시스템에서는 사전에 출발지와 목적지별로 최단경로를 계산해서 최단경로 데이터베이스를 구축해 두고, 이용자로부터 요구가 있을 때 최단경로 데이터베이스를 검색하여 최단경로에 대한 정보를 이용자에게 제공한다. 이러한 기존 시스템은 모든 이용자가 동일한 여건에서 동 데이터베이스를 사용한다는 가정 하에서 만들어진 것으로서, 동일한 이용자라고 하더라도 다쳐서 정상적이지 못하다거나 양손에 짐을 들고 있어서 보행에 불편을 겪는 경우도 있다. 이와 같이 이용자별 다양한 상황을 고려하지 않고 있기 때문에 이용자에게 적합한 최적정보를 제공할 수 없는 문제를 안고 있다. 본 논문에서는 이용자의 다양한 상황을 고려하여 이용자가 출발지와 함께 목적지를 입력하고 동시에 본인의 보행가능상태에 대한 정보를 입력했을 때, 이용자의 보행상태를 고려한 최적정보를 제공하는 알고리즘을 제안한다. 아울러, 본 알고리즘에 대한 시스템을 설계하고 구현하였다. 또한, 최단경로 정보를 구하는데 있어서는 환승역에서의 열차정보도 중요한 정보가 될 수 있는데, 본 최단경로제공 시스템에서는 빠른 환승을 위해 탑승해야 할 열차 차량정보도 같이 제공해 줌으로써 이용자에게 최적의 최단 경로정보를 제공하는 시스템이 될 것이다. 그리고 본 논문에서는 재구성문제에 대한 알고리즘으로서 최단경로 재구성 알고리즘이외에, 깊이 우선 재구성 알고리즘과 폭 우선 재구성 알고리즘 그리고 최소생성트리 재구성 알고리즘을 각각 제안하였다.

A* 알고리즘의 하드웨어 구조 설계

서우진 경북대학교 대학원 2010 국내석사

As people consider that navigator is one of parts of car, it becomes popular. More recently, shortest-path search algorithm on navigator is implemented in software and it is used to inform optimal shortest-path. If this algorithm is implemented in hardware, overall performance efficiency of the automotive navigator system could be improved. This paper proposes a hardware architecture of A* algorithm which is one of the shortest-path search algorithm and shows better performance in finding optimal path and search time. In order to design a hardware architecture of A* algorithm, we model modified shift register and pipeline technique for calculation. The architecture is implemented in C language and its verification is performed with changing the size of map and the value of parameter. After modeling the architecture and verification, I make a design using Verilog HDL and synthesize my work. In this paper, a design of architecture is compared with other researches which are designed with bubble sort to manage a set and calculation block in parallel. Proposed design shows more efficient performance and cost. It is expected that this dissertation gives an idea to make efficient system, especially navigator. And it inspires necessary of shortest-path search hardware. 현재, 내비게이션의 경로 탐색 기능은 소프트웨어로 구현되어 사용자에게 최단 경로를 안내하고 있다. 그러나 다양한 대안 경로의 제시 및 실시간으로 변화하는 도로상황 정보의 적용과 같은 작업을 수행하기 위해서는 소프트웨어의 연산 효율에 추가하여 하드웨어의 도움이 필요로 하다. 경로탐색을 수행하는 전용 하드웨어가 개발되면 소프트웨어의 부담을 줄이면서 시스템의 성능을 향상시킬 수 있다. 이에 본 논문에서는 경로 탐색을 위한 하드웨어 구조를 제안하였다.

유전 알고리즘을 이용한 동적으로 변하는 그래프에 대한 최단 경로 찾기

이정규 서강대학교 대학원 2010 국내석사

본 연구에서는 그래프의 간선 비용이 동적으로 변하는 그래프에 대해서 최단 경로를 찾는 알고리즘에 대해 알아본다. 특히 그래프 상에서 목적지를 향해 일주하는 에이전트가 알 수 있는 그래프의 정보의 범위에 따라 크게 두 가지 접근 방식을 제시한다. 에이전트에게 그래프에 대한 지역 정보(local information)만이 제공될 때, 에이전트는 강화학습을 통해서 동적으로 변하는 그래프에 대한 최적 라우팅 정책(optimal routing policy)을 학습한다. 여기서 지역 정보란 에이전트가 현재 위치하고 있는 노드에 대한 인접 노드의 정보와 인접 노드와의 간선 비용을 의미한다. 에이전트에게 그래프에 대한 고정적인 물리적인 정보(physical information)가 제공될 때에는, 에이전트는 다익스트라 알고리즘을 통해 고정적인 그래프에 대한 최적 라우팅 정책을 학습한다. 여기서 그래프의 물리적인 정보란, 그래프의 노드의 위치 좌표를 의미한다. 위의 두 경우 모두 그래프의 학습 후, 유전자 알고리즘은 결과로 얻은 최적 라우팅 정책과 동적으로 변하는 그래프의 개체군적 정보(populational information)을 이용하여 최단 경로를 계산한다. 여기서 그래프의 개체군적 정보란, 유전자 알고리즘이 경로 계산 시 요구하는 그래프의 정보를 말한다. 본 연구에서는 시뮬레이션을 통해 제안한 알고리즘의 성능을 측정, 검증하였다. In this paper, we present an algorithm to find the shortest path for dynamically changing graphs. The edge costs of a graph are changed dynamically over time. The proposed algorithm consists of two phases: “learning phase” to learn a dynamically changing graph and “adaptation phase” to adapt the current graph conditions using a Genetic Algorithm. There are two cases of learning phase according to the available information on dynamically changing graph: If the agent only has the local information on dynamically changing graph, the it learns the optimal routing policy in learning phase by reinforcement learning. If the agent has the physical information on dynamically changing graph, it learns the optimal routing policy using Dijkstra’s algorithm. After the learning phase, the Genetic Algorithm re-routes the path using the optimal routing policy and the populational information. In experimental results, we show that the proposed algorithm achieves significantly higher scalability for large-scale networks than pure GA-based approaches in the routing problem.

딥러닝을 활용한 병렬화 A 알고리즘의 최적 Queue 개수 산정 연구

설재민 국민대학교 자동차공학전문대학원 2021 국내석사

경로 탐색 분야에 있어서 경로 탐색의 정확성과 경로 탐색까지 소요되는 시간이 중요하다. 경로 탐색이란 출발하려는 출발지에서 도착하려는 도착지까지 이동가능한 경로를 탐색하는 문제를 의미하는 것을 의미하며 이 중 가장 활발히 연구되고 있는 주제는 최단 경로 탐색이다. 최단 경로 탐색 문제에서 지도의 크기가 커져 대형 지도 및 나라, 대도시에 경로 탐색 알고리즘을 적용할 경우 CPU 메모리의 부족 및 리소스 한계 등의 문제로 인해 성능이 급격하게 떨어져 연산시간이 급격하게 저하되는 문제가 발생하게 된다. 이러한 문제를 해결하기 위해 그리드가 서로 다른 두 지도로 나눠 경로 탐색을 진행하여 탐색 시간을 개선하거나 큰 그리드 환경 구조를 활용하여 셀을 두번 이상 방문하지 않는 정확한 근사치를 설정하여 다익스르트 및 A* 알고리즘 보다 빠르게 경로를 탐색하는 등의 방법으로 큰 지도에 대해 성능이 떨어지는 것을 해결한다. 본 논문에서는 미국과 같이 큰 지도에 대한 경로탐색을 빠르게 진행하기 위하여 OSM(OpenStreetMap)에서 제공하는 지도 데이터를 활용하여 병렬 A* 알고리즘을 제안하고 이를 활용하기 위해 딥러닝을 활용하여 최적 경로탐색을 위한 적절한 Queue 갯수를 예측하는 모델을 제안한다. 병렬 A* 알고리즘은 Temporal Array를 사용하여 Extract, Expand, Matching, Insert 총 4개의 과정을 GPU의 병렬 연산을 통해 반복적으로 진행함으로써 중거리이상의 경로에 대해서는 직렬적인 구조를 가진 A* 알고리즘보다 최대 약 80% 빠르게 경로 탐색을 완료하는것을 보였다. 또한, 이를 활용하기 위해 다층 퍼셉트론 모델을 개발하여 경로 탐색 시 필요한 Queue의 갯수를 산정하였으며 해당 모델에 대한 정확도는 약 77% 로, SGD 분류기나 Random Forest 분류기보다 높은 성능을 낸것을 보였다. 향후에는 이러한 정확도를 더 끌어 올리기위하여 총3가지의 연구를 추가로 진행할 계획에 있다. 첫번째로 탐색 속도에 유의미한 영향을 끼치는 feature를 더 발견하는 연구를 진행할 것이다. 두번째로 regression 모델들을 통한 경로 탐색에 최적의 Queue 갯수를 예측하며 본 논문에서 제시한 분류기와의 성능을 비교할 것이다. 세번째로 앞서 진행한 연구들을 토대로 더 정확도가 높은 모델을 선택하며 여러 하이퍼파라미터 튜닝 및 전처리 기법들을 적용하여 정확도를 끌어 올리는 연구를 향후 진행할 예정에 있다. In the field of route search, the accuracy of route search and the time required to route search are important. Path finding refers to the problem of searching for a route that can be moved from the departure point to the destination where you want to arrive, and the subject that is being studied most actively is the shortest route search. In the shortest route search problem, when the route search algorithm is applied to large maps, countries, and large cities, the performance decreases rapidly due to problems such as lack of CPU memory and resource limitations, resulting in a sharp decline in computation time. To solve this problem, the grid is divided into two different maps to improve the search time or to set an accurate approximation that does not visit the cell more than once using a large grid environment structure to solve the poor performance of large maps. This paper proposes a parallel A* algorithm using map data provided by OpenStreetMap (OSM) and proposes a model to predict the appropriate number of queues for optimal route search using deep learning to quickly proceed with route search for large maps like the United States. The parallel A* algorithm has shown that a total of four processes, Extract, Expand, Matching, and Insert, are repeatedly performed through parallel operations of GPUs using Temporal Array, completing the path search up to 80% faster than the A* algorithm with a serial structure. In addition, to utilize this, a multi layer perceptron model was developed to calculate the number of queues required for route search, and the accuracy of the model was about 77%, showing higher performance than the SGD classifier or Random Forest classifier. In the future, these more accurate to raise a total of three studies in planning to make further progress.First, a significant impact on the navigation speed feature the research to find more.The second path on a quest through the optimal models regression queue to predict the number and will compare performance with the classification provided for in this paper.A third of the first couple of more studies on the basis of pretreatment techniques and tuning parameters of Various Hypervisors, and select models that are so accurate it elevates the accuracy by applying research in will be following.

오버레이 멀티캐스트 트리구성을 위한 변형된 Dijkstra 알고리즘

이형옥 전남대학교 대학원 2008 국내석사

화상 회의, 인터넷 방송 등의 실시간 응용 시스템을 위해 오버레이 멀티캐스트 트리가 충족 시켜야 하는 조건은 크게 두 가지이다. 첫 번째는 호스트, 즉 트리 상의 노드의 차수가 적절한 상한이어야 한다는 것이다. 트리 상의 특정 노드의 차수가 지나치게 높다는 것은, 그 사용자가 접속하고 있는 네트워크 상의 링크로 동시에 많은 데이터를 보내 주어야 하기 때문에 대역폭의 한계로 인해 각각의 이웃 사용자에 대한 전송 속도가 떨어지고, 패킷 손실률이 증가한다는 것을 의미한다. 두 번째 조건은, 멀티캐스트 트리의 지름, 즉 트리 상의 경로 거리로 볼 때 가장 먼 두 사용자 간의 거리가 작아야 한다는 것이다. 두 사용자 간의 트리 상의 경로 거리가 길면 두 사용자 간에 데이터를 보낼 때의 지연 시간이 커지기 때문에, 화상 회의와 같은 응용 시스템에 적합하지 않게 된다. 각 노드의 차수가 상한을 가지고 있을 때 지름이 최소인 트리를 구성하는 문제는 NP-complete 문제로 알려져 있다. 본 논문에서는 다익스트라 알고리즘의 Cost값을 오버레이 멀티캐스트 트리를 구성하는 노드들의 가용대역폭과 이웃노드들과의 Delay, 그리고 요구대역폭을 체크한 후, 제안하는 Score Function을 적용하여 계산한다. 그리고 그 값을 다익스트라 알고리즘에 적용하여 트리를 구성하게 된다. Conditions that overlay multi cast tree must satisfy for real-time application system of a video-conference, an internet broadcasting is two things. First, a degree of nodes in tree must be proper value. That degree of some node in a tree is high means that the node must send many data at the same time to links in the network that the user is connecting. So, transmission speed drops to each neighborhood user by limit of the bandwidth, and the packet-loss rate increases. Second, diameter of multicast tree, distance between longest two users should be short. If path between two users in the tree is long, the delay time in data transmission between two users great. So, it is not suitable to the application system such as video-conferences. In this paper, the cost of the dijkstra algorithm calculate with proposed score-function through checking the extra bandwidth, the delay and the requested bandwidth. It is composed the tree through the dijkstra algorithm.

3차원 최단거리 탐색을 위한 A* 알고리즘 연구

김경환 中央大學校 尖端映像大學院 2016 국내석사

Starcraft 나 LOL ( League Of Legend ) 와 같은 전략 시뮬레이션 게임, FPS( First Person Shooter )같은 1인 슈팅 게임은 최단 거리를 어떻게 찾는가? 그러한 게임들이 좀 더 빠른 최단 거리를 방법을 찾으면 게임은 어떠한 재미를 선사할 것인가? 라는 질문에서 본 논문의 연구가 시작되었다. A* 알고리즘은 최단 거리를 찾아내는 탐색 알고리즘의 하나로 기존의 3차원 환경에서도 2DA*를 사용해서 경로를 탐색하였는데, 3차원에서는 3차원에 적합한 알고리즘을 사용해야 하는 것이 더 효율적임을 제안한다. 실험을 위해 Unity3D 게임 엔진을 이용하여, 2DA* 와 3DA*를 구현하였다. 그리고 2DA* 와 3DA*의 효율을 측정할 수 있는 방법을 5x5x5 또는 10x10x10 환경을 만들어 비교 실험을 통해 검증 하였다. 만들어진 3DA*를 활용하기 위해서 minecraft 와 비슷한 게임을 만들어 실험을 하였고, 2DA* 와 비교하여 3DA*가 가지는 장점을 이용해서 그래픽의 확산 시뮬레이션으로 활용하였다. Starcraft or LOL (League Of Legend) with the same strategy simulation game, FPS (First Person Shooter) such person shooters How do you find the shortest distance? Games find a way to get faster shipping shortest game will be any fun?   A * algorithm were through the route using 2DA * in the conventional three-dimensional environment as one of the search algorithm to find the shortest distance, three-dimensional, we propose that it is more efficient to use a suitable algorithm to 3D.   Using the Unity3D game engine for the experiment, 2DA * 3DA * and we have implemented. 3DA and 2DA * and * in a way to measure the efficiency or create a 5x5x5 10x10x10 environment was verified by comparative experiments. Similar experiments were made with the minecraft game to take advantage of the built 3DA *, compared to the 3DA 2DA * * was used as a graphic of the diffusion simulation by the advantages.

최적 경로 탐색을 이용한 자전거 경로 선정에 관한 연구

백승헌 전남대학교 대학원 2012 국내석사

본 연구에서는 지형공간요소와 최적 경로 알고리즘을 이용하여 자전거 경로 선정을 연구하였다. 네트워크 상에서 최단경로를 찾는 알고리즘 중에서 일반적으로 널리 알려진 알고리즘이 다익스트라(dijkstra) 알고리즘이다. 자전거 최적경로 탐색을 위해선 잔여거리를 고려하지 않고 정점과의 최단거리만 고려해서 선택하는 다익스트라 알고리즘보단 최단거리와 잔여거리 함수를 사용해 판단을 하는 A*(a-star)알고리즘에 대한 연구가 필요하다. 자전거 최적 경로 선정을 위하여 자전거 경로 선정 요소를 도출하고, 경사에 따른 수평거리와 평균 속도를 계산하였다. 다익스트라 알고리즘과 A* 알고리즘을 적용해 최단거리와 최단시간에 따른 자전거 경로 선정을 하였다. 연구 결과 GIS를 활용한 자전거도로의 최적 경로를 선정하기 위해서는 다양한 출발점과 도착점을 연결할 수 있는 네트워크가 구축되어야 한다. 대규모 지역에서 선정된 경로는 A* 알고리즘이 다익스트라 알고리즘보다 처리 시간이 빠르게 나타났다. 향후 최적 경로 선정 알고리즘은 실시간 모바일 서비스나 차량용 내비게이션을 이용한 최적 경로 선정 시 빠른 검색 방법으로 이용될 수 있을 것이다. This study was to examine bike route selection using geo-spatial elements and optimal path algorithm. Well-know algorithm of algorithms to find the shortest path on the network is dijkstra algorithm. The research on A*(a-star) algorithm to determine using the shortest distance and the remaining distance function is needed rather than dijkstra algorithm to determine to select considering only the shortest distance with apogee without considering the remaining distance for bike's optimal path search. The factors of bike route selection were derived for bike's optimal path selection, the horizontal distance and average speed depending on the slope were calculated. Bike route was chosen according to the shortest distance and time using dijkstra and A*(a-star) algorithm. As a result, the networks to connect various departure points and arrival points should be established to choose optimal route of bike lanes using GIS. A*(a-star) algorithm chosen in large areas showed to be faster in processing time than dijkstra algorithm. In future, optimal path selection algorithm will be able to be used as selecting optimal path using real-time mobile services or car navigation.

RC 플랫폼을 이용한 지역경로생성 시뮬레이션 연구

김상정 국민대학교 산업기술대학원 2009 국내석사

본 논문에서 소개하는 RC (Remote Controller)플랫폼은 GPS (Global Positioning System)수신기, 디지털 나침반 (digital compass), CMOS USB 카메라와 블루투스 시스템 등으로 이루어져 있다. 이 RC플랫폼은 개발한 알고리즘을 실제 무인자율차량에 대입하기 이전에 RC플랫폼에 프로 그램을 대입하여 실험 하기 위한 장비이다. 본 연구는 RC플랫폼을 통해서 무인자율차량을 개발하는데 필요한 시스템을 구현하고 무인자율차량 시스템의 안전성과 안전성 향상을 위한 연구를 하는데 목적이 있다. 기존의 원격무인차량은 원격제어부의 제어 명령에 따른 차량의 주행 제어를 하며 또한 장애물 인식 시스템의 장애물 위치 정보 및 원격 제어 시스템의 제어명령을 통합 처리하여 무인자율차량의 주행 안정성을 고려하여 개발해 왔다. 하지만 RC플랫폼은 GPS수신기, 디지털 나침반의 신호를 통해 기록된 정보, 현재위치, 경로점, 도착점 등의 장애물 정보를 가지고 일정한 형식의 맵 (map)을 형성하였다. 이 맵을 통해A* 알고리즘과 D* 알고리즘을 기반으로 경로계획 (path planning)알고리즘에 입력되어 저 비용의 주행 경로를 생성하게 되며, 이 경로를 주행하는 것을 시뮬레이션으로 나타내었다. The RC (Remote Controller) platform introduced in this thesis is made up of the GPS (Global Positioning System) receiver, digital compass, CMOS USB camera and bluetooth system. This RC platform is the equipment to apply program to the RC platform before applying developed algorism to actual Unmanned Vehicle. This research has a purpose to materialize the system needed to develop unmanned vehicle through RC platform, and to improve the safety of unmanned vehicle system. The Previous remote unmanned vehicle controlled the vehicle driving under the command of remote controller system. Also, it has been developed by integrated managing the obstacle positioning information from obstacle identification system and the control instruction of remote controller system, considering the driving safety of unmanned vehicle. However, the RC platform with the obstacle information of the present position, route, arrival point, etc recorded by signal of the GPS receiver and digital compass forms a map in a regular format. Through this map, I input the path planning into the algorism based on A* algorism and D* algorism and then, create the driving route at a low cost and visualize driving in this route by the method of simulation.