변형된 점증 깊이 우선 탐색 방법을 사용한 로봇 계획 시스템

임재걸,Yim, Jae-Geol 한국정보처리학회 1995 정보처리논문지 Vol.2 No.3

본 논문은 목적 상태를 구성하는 부분목적들 사이의 선취관계를 이요하는 새로운 탐색방법을 제안한다.제안된 방법은 기존의 인공지능 탐색 방법에 부분 목적들간의 선취관계를 이용하여 분지인수(branching factor)와 탐색 공간의 깊이를 줄이고,직접 성취 가능한 극대 부분 목적과 필연적인 작업들을 즉시 실행하는 전략을 사용하여 효율성을 더육 제고 시킨다. 이러한 전략을 사용하는 제안된 알고리즘의 효율성을 이론적으로 보일 뿐 아니라,점증깊이 우선 탐색(DFID:Depth-First Iterative Deepening Search)방법과 IDA(Iteratice Deepening A)알고리즘에 제안도니 방법을 적용하여 얻은 변형된 탐색 알고리즘을 이용하는 로봇 계획 시스템을 구현하여 제안된 전략의 효율성을 실험적으로도 보인다. We propose a new search method which is based on the precedence relationship between subgoals.The prosed method reducess both the branching factor of and the depth of the search space by making use of the precedence relationship between subgoals, and further improves the efficiency of A.I.search by immediately achieving directly achievable maximal subgoals and immediately performing the directly applicable actions which must be eventually done.The efficiency of our method has been analysed theoretically.We have also implemented a robot planning system equipped with versions of DFID and IDA which are modified by applying our proposed strategies, and experimentally showed the efficiency of our strategy.

하이퍼미디어 시스템 탐색의 최적 스케쥴을 찾는 통계적 페트리 넷을 이용한 새로운 패러다임

임재걸,변정용 동국대학교 경주대학 1997 東國論集 Vol.16 No.1

Information providers on WWW have comprehensive meta-knowledge of their information: For each data unit, they know the size of data, time needed to read, the subject of the data, the objective value of the data, how close it is to the original information, and so on. With this comprehensive meta-knowledge, an information provider can find an optimal schedule of information exploration for the users. A schedule is a sequence of hypermedia scenarios,where as a hypermedia scenario is a sequence of hyperlinked multimedia data units. A schedule is legal if the schedule can be finished within a given time. A legal schedule is optimal if it gives the maximum satisfaction to the user. This paper proposes a new paradigm to find such an optimal schedule. We assume that the data units are graded on certain criteria. For example, a piece of data is about an architectural "national treasure" whereas another one is about a "general treasure". With this grades and the degree of closeness to the original information, we can get the degree of potential user's satisfaction. Now, we need the time required to finish a hypermedia scenario. As a method to find such a time, we propose a stochastic Petri net method. Our stochastic Petri net method first builds a Petri net model of a hypermedia scenario. A data unit is presented as a place in a Petri net. Out going arc form a place is mapped with a "spent time distribution table". Therefore, we can perform Monte Carlo simulation to estimate the time needed to go through the Petri net from the start place to the final place. The estimated time is the time required to finish the hypermedia scenario. Once we have user's satisfaction p and time required to read t for each hypermedia scenario, then an optimal schedule is the sequence of scenarios in the order of p/t.

상자 세계 문제의 로봇계획을 찾는 매우 빠른 알고리즘

임재걸,이계영 동국대학교 경주대학 1994 東國論集 Vol.13 No.-

It is well known that building an efficient general purpose robot planner is an almost impossible task. Therefore, we are concentrating on a particular planning problem. One of the most famous robot planning problems is Bloks World Problem, and the problem is proved to be NP-complete[6]. That is, if it can be solved, then many other practically usefull but difficult problems can be also solved. We first present a few facts representing the characteristics of Blocks World problem. Based on the facts, we come up with a very fast algorithm which finds plans for Blocks World problems. Basic design ideas for the algorithm and experimental test results of the algorithm are also presented.

옥내 측위를 위한 지문 방식 알고리즘들의 성능 분석

임재걸 대한전자공학회 2006 電子工學會論文誌-CI (Computer and Information) Vol.43 No.6

For the indoor positioning, wireless fingerprinting is most favorable because fingerprinting is most accurate among the techniques for wireless network based indoor positioning which does not require any special equipments dedicated for positioning. The deployment of a fingerprinting method consists of off-line phase and on-line phase. Off-line phase is not a time critical procedure, but on-line phase is indeed a time-critical procedure. If it is too slow then the user’s location can be changed while it is calculating and the positioning method would never be accurate. Even so there is no research of improving efficiency of on-line phase of wireless fingerprinting. This paper proposes a decision-tree method for wireless fingerprinting and performs comparative analysis of the fingerprinting techniques including K-NN, Bayesian and our decision-tree. 무선네트워크 기반 옥내측위는 측위를 위한 특수 장비를 필요로 하지 않고, 지문 방식은 무선네트워크 기반 측위를 위한 기술 중에서 가장 정확도가 높기 때문에 무선네트워크 지문 방식이 가장 적당한 옥내측위 방법이다. 지문 방식은 준비 단계와 실시간 측위 단계로 구성되는데, 준비 단계는 그렇지 않지만 실시간 측위 단계는 실행 시간이 매우 중요한 요소인 작업이다. 왜냐하면, 실시간 측위 단계의 실행 시간이 너무 길면, 실행 도중에 사용자가 너무 많이 이동하여 정확한 측위가 불가능하게 되기 때문이다. 그럼에도 불구하고 무선네트워크 기반 지문 방식의 실시간 측위 단계의 효율성을 개선하는 연구는 아직 수행된 바가 없다. 이 논문은 무선네트워크 기반 지문 방식을 위한 판단나무 방법을 제안하며, 기존의 K-NN 방법 그리고 베이지안 방법과 본 논문이 제안하는 판단나무 방법을 정확도와 실행 시간 측면에서 비교 분석한다.

이동물체 데이터베이스의 페트리 넷 모형

임재걸,이계영 대한전자공학회 2004 電子工學會論文誌-CI (Computer and Information) Vol.41 No.03

현재 이동물체 데이터베이스에 관한 연구가 활발히 진행되고 있다. 그러나 기존 연구의 대부분은 갱신 전략의 효율성 증대에 초점이 맞추어져 있고, 이동물체 데이터베이스 시스템의 사용자 요구사항 검증에 대한 연구 논문은 전무하다. 아무리 효율성이 좋은 갱신 전략이 적용되었더라도, 시스템 설계자는 시스템이 사용자 요구사항을 만족하는지에 대해 개발초기에 반드시 검증을 해 보아야 한다. 예를 들어, 이동물체가 n개이면, n개에 대한 데이터베이스 정보 갱신 작업과 새로운 정보를 사용자에게 제공하여주는 작업을 정해진 시간 내에 완료할 수 있는지 개발 초기에 검증해야 하는 것이다. 본 논문은 이동물체 데이터베이스의 요구사항 분석을 위하여, Design/CPN이라는 시뮬레이션 도구를 이용하여 페트리 넷 모형을 구축하고, 시뮬레이션을 통하여 사용자 요구사항을 검증하는 방법을 소개한다. 본 논문은 이동물체 데이터베이스의 사용자 요구 분석을 위한 최초의 시뮬레이션 모델을 제공하는데 의의가 있다. 이 시뮬레이션 모델은 본 저자가 이미 발표한 퍼지시간 페트리 넷 모형에 대해 거리기반 갱신전략과 분산 데이터베이스 모형을 첨가 확장한 것이며, n 개의 이동물체를 고려한 분석 결과를 소개한다. 또한, 본 모형은 Design/CPN이라는 시뮬레이션 도구로 구축되었기 때문에 시스템에 대한 자동분석이 가능하다. 본 모형의 응용 범위는 사용자 요구사항 분석에 국한된 것이 아니라, 갱신 비용과 정보의 정확도 간, 혹은 갱신에 소요되는 시간과 자원 간의 상관관계를 분석하는 데에도 유용하게 쓰인다. Quite many papers about moving objects database (MOD) have been published. Most of them are concerning of improving efficiency of updating policy, but none of them talks about verification of system's requirements. No matter how efficient updating policy is employed, a system designer still has to verify if the MOD satisfies user's requirement at the beginning of system lifecycle. For example, if a MOD serves n moving objects, then the designer must verify if it can update information for n moving objects and provide new information to nmoving objects within specified time limit. For the purpose of requirement analysis of MODs, we build a Petri net model for MOD using Design/CPN, and then we show how to verify whether the MOD satisfies user's requirements by simulation. The contribution of this paper is providing a simulation model for requirement analysis of MOD for the first time. The model is expansion of our previous fuzzy-timing Petri net model. The distance-based updating policy, and distributed database management system are reflected in this model and system analysis for nmoving objects is considered. It is built in Design/CPN so that the simulation can be automatically performed. The application of our model is not limited to requirement analysis, it is useful to study other MOD design issues, such as the trade-offs between update cost and information accuracy, and between the time interval needed for updating database and MOD system resources, etc.

장소-변천망의 구조적 특징 분석기 구현

임재걸 동국대학교 경주대학 1993 東國論集 Vol.12 No.-

Since the 1960's, Petri nets have been used for modelling and analysis of concurrent systems, including communication protocols, distributed-software systems, distributed-database systems, concurrent and parallel programs, flexible manufacturing /industrial control systems and so on. This is mainly due to the modelling capability of Petri nets. However, There is a tradeoff between modelling generality and analysis capability. In fact, a major weakness of Petri nets is the complexity problem. Thus, the use of computer-aided tools is a necessity for practical applications of Petri nets. As the usage area of Petri net grows, various versions of Petri net have been introduced. In order to distinguish the original Petri net from the other new versions, we call the original Petri net a place-transition net. This paper presents algorithms to analyze place-transition net's idea of this algorithm stems from [MS81] which deals with S-Invariants. Siphons and traps are essential elements in analysis of a free-choice net (a subclass of place-transition nets). This paper also presents new analysis methods of structural properties of Petri nets. These methods have been implemented as a part of Petri net analysis system.

로봇계획을 찾는 인공지능 탐색의 효율성 제고 방법

임재걸 동국대학교 경주대학 1996 東國論集 Vol.15 No.-

An Associate Professor of Dept. of Computer Science, College of Natural Science A robot planning system is a computer program which finds a sequence of actions which changes the current configuralion to the goal configuration if performed by the robot in the sequence. Many different kinds of robot planning systems have been proposed, designed, and constructed. But the fundamantal technique on which all the robot systems have been based is artificial intelligence (AI) search. In this paper we propose techniques to improve the efficiency of AI search. The proposed techniques are based on the precedence relation betWeen subgoaIs. We first identify the interference relation between actions which might be a part of the plan. With the interference relation we identify the precedence relation between subgoals. By pruning search branches which violate the precedence relation, we can reduce the size of search space. Expenemental results which show the effectiveness of our techniques are provided.

페트리네트를 이용한 멜티미디어 시스템 시나리오 작성기 설계

임재걸,이계영 동국대학교 경주대학 1998 東國論集 Vol.17 No.1

This paper proposes a design method for a multimedia scenario editor. Our method is based on Petri net theory. Existing Petri nets do not have facility of modeling asynchronous flow of multimedia scenario. Therefore, we propose a modified Petri net called MPN(multimedia Petri net) which is equipped with the facility of modelling asynchrnous flow. Our scenario editor provides a convenient environment for constructing an MPN model to the users. An MPN model not only shows scenario flow information but also includes all the information about data presentation. Therefore, an MPN can be translated into a multimedia program which plays specified scenario. This paper presents an efficient algorithm for the translation. This paper investigates MPN's properties which can be used for verifying a scenario presented as an MPN. For example, an MPN should be safe. An algorithm to check if an MPN is safe is presented in this paper.

안드로이드 측위 앱 개발

임재걸,전준리 사단법인 인문사회과학기술융합학회 2014 예술인문사회융합멀티미디어논문지 Vol.4 No.2

근래에는 스마트폰이 매우 널리 보급되어 거의 누구나 스마트폰을 이용한다. 그리고 스마트폰은 필수품이 되어 항상 휴대하고 다닌다. 근래에는 스마트폰의 계산능력과 기억용량이 현저하게 발달되어 다양한 응용프로그램을 실행할 수 있게 되었다. 나아가서 스마트폰에 상당히 정확한 GPS(Global Positioning System) 수신기가 장착되어 있다. 관광지에서 사용자의 위치를 고려하여 유용한 정보를 제공하면 관광객에게 큰 도움을 줄 수 있기 때문에, 본 연구는 안압지 내에서 사용자가 관심지점에 위치한 상황을 정확하게 판정하는 안드로이드 앱을 소개한다. Nowadays, smart-phones are so widely spread that almost everybody has a smart-phone. A smart-phone is an absolute necessity and everybody carries one around all the time. As the computing power and memory capacity have been significantly improved, various applications are now available on smart phones. Furthermore, most smart phones are equipped with very accurate GPS (Global Positioning System) receivers. Tourists’ satisfaction can be significantly enhanced if location based useful information is provided to them. This paper introduces an Android app that 100% correctly recognizes a user’s position when the user locates at a point of interest in Anapji, a famous artificial pond in Gyeongju National Park.

하이퍼미디어 수행 시간을 예측하는 새로운 방법

임재걸,이계영 동국대학교 경주대학 2000 東國論集 Vol.19 No.-

The execution times of hypermedia scenarios are useful to both information providers and end users. Using the information of execution times, an end user can make a better use of his time and an information provider can create more efficient scenario-presentation schedule for users. To estimate the execution time of a hypermedia scenario, Montecarlo simulation method was introduced in [1]. In this method, we perform thousands or more trials before coming up with a time estimation. To avoid these many time consuming trials, we are introducing a new method. With the new method we can find the probabilistic expectation value of a scenario's execution time. We are performing experiments to compare our method against Montecarlo method.