제약식 있는 동적계획법의 해법 연구 - 장기 자동차 렌탈 문제를 중심으로

박태준(Tae Joon Park),김학진(Hak-Jin Kim),김진희(Jinhee Kim) 한국컴퓨터정보학회 2021 韓國컴퓨터情報學會論文誌 Vol.26 No.12

본 연구에서 제약식프로그래밍을 이용하여 제약식 있는 동적계획법 모형을 푸는 한 방법을 제시한다. 현재 제약식 있는 동적계획법을 다루는 방법은 각 단계별 제약식들의 상태를 일반적인 동적계획법의 상태공간에 추가하여 마치 제약식이 없는 동적계획법 방식을 적용하는데 반해, 이 연구에서 제시하는 방식은 제약식의 상태가 제약식프로그래밍의 변수 도메인으로 표현되고 저장된다. 계산에 있어서도 일반적인 동적계획법의 벨만방정식의 해법과 함께 제약식을 다루기 위한 제약식프로그래밍의 확산-추론 방법을 사용하는 하이브리드 방식을 따른다. 이 두가지 방식의 비교를 위해 특별히 장기 자동차 렌탈 문제를 제시하고 이 문제의 단순화된 모형을 중심으로 다른 방식으로 해결하는 과정을 보고 그 장단점을 논한다. In this paper, a new approach to solve the constrained dynamic programming is proposed by using the constraint programming. While the conventional dynamic programming scheme has the state space augmented with states on constraints, this approach, without state augmentation, represents states of constraints as domains in a contraining programming solver. It has a hybrid computational mechanism in its computation by combining solving the Bellman equation in the dynamic programming framework and exploiting the propagation and inference methods of the constraint programming. In order to portray the differences of the two approaches, this paper solves a simple version of the long-term car rental financing problem. In the conventional scheme, data structures for state on constraints are designed, and a simple inference borrowed from the constraint programming is used to the reduction of violation of constraints because no inference risks failure of a solution. In the hybrid approach, the architecture of interface of the dynamic programming solution method and the constraint programming solution method is shown. It finally discusses the advantages of the proposed method with the conventional method.

EP Based PSO Method for Solving Multi Area Unit Commitment Problem with Import and Export Constraints

K. Venkatesan,G. Selvakumar,C. Christober Asir Rajan 대한전기학회 2014 Journal of Electrical Engineering & Technology Vol.9 No.2

This paper presents a new approach to solve the multi area unit commitment problem (MAUCP) using an evolutionary programming based particle swarm optimization (EPPSO) method. The objective of this paper is to determine the optimal or near optimal commitment schedule for generating units located in multiple areas that are interconnected via tie lines. The evolutionary programming based particle swarm optimization method is used to solve multi area unit commitment problem, allocated generation for each area and find the operating cost of generation for each hour. Joint operation of generation resources can result in significant operational cost savings. Power transfer between the areas through the tie lines depends upon the operating cost of generation at each hour and tie line transfer limits. Case study of four areas with different load pattern each containing 7 units (NTPS) and 26 units connected via tie lines have been taken for analysis. Numerical results showed comparing the operating cost using evolutionary programming-based particle swarm optimization method with conventional dynamic programming (DP), evolutionary programming (EP), and particle swarm optimization (PSO) method. Experimental results show that the application of this evolutionary programming based particle swarm optimization method has the potential to solve multi area unit commitment problem with lesser computation time.

Efficient Dynamic Object-Oriented Program Slicing

Park, Soon-Hyung,Park, Man-Gon Korea Multimedia Society 2003 멀티미디어학회논문지 Vol.6 No.4

Traditional slicing techniques make slices through dependence graphs. They also improve the accuracy of slices. However, traditional slicing techniques require many vertices and edges in order to express a data communication link because they are based on static slicing techniques. Therefore the graph becomes very complicated, and size of the slices is larger. We propose the representation of a dynamic object-oriented program dependence graph so as to process the slicing of object-oriented programs that is composed of related programs in order to process certain jobs. We also propose an efficient slicing algorithm using the relations of relative tables in order to compute dynamic slices of object-oriented programs. Consequently, the efficiency of the proposed efficient dynamic object-oriented program dependence graph technique is also compared with the dependence graph techniques discussed previously As a result, this is certifying that an efficient dynamic object-oriented program dependence graph is more efficient in comparison with the traditional object-oriented dependence graphs and dynamic object-oriented program dependence graph.

Dynamic Programming을 적용한 트리구조 미로내의 목표물 탐색 알고리즘

이동훈(Dong-Hoon Lee),윤한얼(Han-UI Yoon),심귀보(Kwee-Bo Sim) 한국지능시스템학회 2005 한국지능시스템학회논문지 Vol.15 No.5

본 논문에서는 Dynamic Programming(DP)을 적용한 트리구조 미로내의 목표물 탐색 알고리즘을 구현한다. DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적해를 이용하여 순환적으로 큰 문제를 해결한다. 먼저 실험을 위해 적외선 센서를 부착한 소형 이동 로봇과, ‘Y’형태로 갈라진 걸을 연결한 트리 구조의 미로 환경을 구성한다. 실험에서는 두 개의 서로 다른 알고리즘 - 좌수법, DP - 을 사용하여 목표물 탐색을 시도한다. 마지막으로 위 실험을 통해 DP를 미로 탐색문제에 적용했을 때의 성능을 검증한다. This paper presents the target object search algorithm under dynamic programming (DP) in the Tree-type maze. We organized an experimental environment with the concatenation Y-shape diverged way, small mobile robot, and a target object. By the principle of optimality, the backbone of DP, an agent recognizes that a given whole problem can be solved if the values of the best solution of certain ancillary problem can be determined according to the principle of optimality. In experiment, we used two different control algorithms: a left-handed method and DP. Finally we verified the efficiency of DP in the practical application using a real robot.

Gaussian Process Approximate Dynamic Programming for Energy Management of Parallel Hybrid Electric Vehicles

Jin Woo Bae,Dohee Kim,Jeongsoo Eo,Kwang-Ki K. Kim 제어로봇시스템학회 2020 제어로봇시스템학회 국제학술대회 논문집 Vol.2020 No.10

This paper presents two non-parametric Bayesian techniques–Gaussian Process Dynamic Programming (GPDP) and Gaussian Process Dynamic Programming-Receding Horizon Control (GPDP-RHC)–for optimal energy management of parallel hybrid electric vehicles. Hybrid electric vehicles (HEVs) are powered by engine and electric machine and assigning the required traction power to the two sources. It is known as the supervisory control which can be formulated as an optimal control problem. To solve the supervisory optimal control, we adopt the approximate dynamic programming (ADP) with Gaussian processes (GPs) which are used for value function approximation in optimal control problem. High-fidelity models of real-world vehicle data for battery, engine, and electric machine are used to obtain discrete dynamic programming (DP) solutions for a known driving cycle. To overcome limitations in real-time application of DP, we use non-parametric Bayesian function approximation techniques using GPs. The state-value tables obtained by dynamic programming are approximated by Gaussian process regression. Furthermore, the future value function is predicted by GPDP in one-step lookahead with RHC. For demonstration of optimality and efficiency, the proposed GPDP-RHC solution is compared with both the offline global DP solution and real-driving result.

Energy Management Strategy of Hybrid Electric Vehicle Using Battery State of Charge Trajectory Information

이희은,차석원,정종렬,박영일 한국정밀공학회 2017 International Journal of Precision Engineering and Vol.4 No.1

This paper presents a new energy management control strategy of a hybrid electric vehicle, using dynamic programming with preview driving cycle information. Dynamic programming is a promising solution for energy management problem of the hybrid electric vehicle, yet global optimality can only be achieved with preview driving cycle information due to its non-causal property. As recent driving cycle prediction algorithms facilitate the use of preview driving cycle information, rule-based energy management strategy of the hybrid electric vehicle using dynamic programming optimization is presented in this study, under the assumption that the preview driving cycle information is already given. The strategy is composed of dynamic programming calculation and the rule-based control strategy using that calculation. Dynamic programming analyzes optimal control and battery state of charge trajectory in accordance with the vehicle travel distance, with given predicted driving cycle information. The proposed rule-based strategy distributes vehicle’s demand power into the engine and the electric motor, to follow target battery state of charge trajectory acquired from dynamic programming. To validate the control strategy, simulation is conducted on various standard driving cycles. The energy management strategy shows improved fuel economy performance for diverse driving cycles.

동적계획법과 적응 비용 변환을 이용한 영상 모자이크의 seam-line 결정

전재춘,서용철,김형석 한국지리정보학회 2004 한국지리정보학회지 Vol.7 No.2

영상 모자이크 작업에서 두 영상 간의 경계선이 보이지 않는 최적의 seam-line을 구하기 위해 화소값 차이 변환과 동적계획법 이용 알고리즘을 제안하였다. 영상 간의 경계선은 두 영상의 화소값 차이가 적은 화소를 따라 형성되는 것이 시각적 부담이 적다. 이 화소들을 연결하는 것은 최적경로를 찾는 알고리즘을 이용할 수 있다. 최적 경로 결정에 효과적인 동적계획법을 seam-line 결정에 직접 적용하면 화소값의 차이뿐만 아니라, seam-line의 길이에 따라 영향을 받는 거리영향문제가 발생한다. 이 논문에서는 적응적 변환함수를 사용하여 비용 변환을 수행하고, 변환된 비용공간 상에서 동적계획법을 적용하여 거리영향이 억제된 최적 seam-line을 구할 수 있는 알고리즘을 개발하였다. 또한 결정된 seam-line을 평가하기 위해 일정한 개수의 상위 화소값의 차이를 누적한 값(SFBPD)을 척도로 제시하였다. 제안한 seam-line 결정방법을 다양한 종류의 영상에 대해 적용 실험하였으며, 시각적 및 SBPD 값에 의한 수치적 결과를 제시하였다. A seam-line determination algorithm is proposed to determine image border-line in mosaicing using the transformation of gray value differences and dynamic programming. Since visually good border-line is the one along which pixel differences are as small as possible, it can be determined in association with an optimal path finding algorithm. A well-known effective optimal path finding algorithm is the Dynamic Programming (DP) . Direct application of the dynamic programming to the seam-line determination causes the distance effect, in which seam-line is affected by its length as well as the gray value difference. In this paper, an adaptive cost transform algorithm with which the distance effect is suppressed is proposed in order to utilize the dynamic programming on the transformed pixel difference space. Also, a figure of merit which is the summation of fixed number of the biggest pixel difference on the seam-line (SFBPD) is suggested as an evaluation measure of seamlines. The performance of the proposed algorithm has been tested in both quantitively and visually on various kinds of images.

EP Based PSO Method for Solving Multi Area Unit Commitment Problem with Import and Export Constraints

Venkatesan, K.,Selvakumar, G.,Rajan, C. Christober Asir The Korean Institute of Electrical Engineers 2014 Journal of Electrical Engineering & Technology Vol.9 No.2

This paper presents a new approach to solve the multi area unit commitment problem (MAUCP) using an evolutionary programming based particle swarm optimization (EPPSO) method. The objective of this paper is to determine the optimal or near optimal commitment schedule for generating units located in multiple areas that are interconnected via tie lines. The evolutionary programming based particle swarm optimization method is used to solve multi area unit commitment problem, allocated generation for each area and find the operating cost of generation for each hour. Joint operation of generation resources can result in significant operational cost savings. Power transfer between the areas through the tie lines depends upon the operating cost of generation at each hour and tie line transfer limits. Case study of four areas with different load pattern each containing 7 units (NTPS) and 26 units connected via tie lines have been taken for analysis. Numerical results showed comparing the operating cost using evolutionary programming-based particle swarm optimization method with conventional dynamic programming (DP), evolutionary programming (EP), and particle swarm optimization (PSO) method. Experimental results show that the application of this evolutionary programming based particle swarm optimization method has the potential to solve multi area unit commitment problem with lesser computation time.

차량 동역학 측면에서의 동적 전복 특성에 관한 연구

장진희(Jin-Hee Jang),존 캐리에(John A. Carriere) 한국자동차공학회 2004 한국자동차공학회 춘 추계 학술대회 논문집 Vol.- No.-

In this paper, an approach on the dynamic rollover characteristics has been introduced and explained using some of the latest information from NHTSA. A new NCAP test has been announced by NHTSA including Static Stability Factor and Fish-Hook test which is a dynamic test for the prediction of dynamic rollover propensity. From 2004, a new star rating on rollover propensity results of new cars has been issued by NHTSA to US customer. Until now the rating is an only reference data for the purchasing process of customer. Basically, it is not a regulation item of car makers, but information for the selecting their own cars. This rating is an index for the rollover risk for each vehicle. In the near future, this rating may be a critical data for the sales of cars in US, especially, for SUV. Therefore, we have to understand the status of rollover related research in the world and have to prepare with the change of market requirements and information of customer. This dynamic rollover related topic is a research area of vehicle dynamics parts before crash and rollover. The star rating on the rollover is based on the huge rollover crash information and vehicle basic dimension like as tread and height of center of gravity data. Also, a dynamic test result has been adopted as a scaling factor for the compensation of static criteria for the decision making on the rollover propensity. The start point on this approach for rollover related topic is the exact measuring basic dimensions and the clear understanding of rollover mechanics based on vehicle dynamics. We have to make a development strategy for the consideration of rollover at the early design stage before the major freezing. Finally, basic rollover mechanics, parameters of dynamic rollover, strategy on rollover mechanics, and the state-of-the-art of dynamic rollover related topics are introduced in this paper.

A Stereo Matching Algorithm based on Top-view Transformation and Dynamic Programming for Road-vehicle Detection

이기용,Nasser Houshangi,이준웅 제어·로봇·시스템학회 2009 International Journal of Control, Automation, and Vol.7 No.2

This paper presents an algorithm to detect vehicles on roads and to measure inter-vehicle distance. Hypothesis generation and verification are the bases of the algorithm. The hypothesis generation is composed of 1) transformation of a pair of perspective stereo images into a pair of virtual stereo top-view images; 2) construction of polar accumulation functions (PAFs) for the stereo top-view images; and 3) stereo matching of PAFs by dynamic programming. The verification is comprised of 1) temporal matching of PAFs by dynamic programming and 2) verifying the potential positions of ob-jects. Through multiple experiments in various environments, the proposed algorithm has been proven to be effective in detecting vehicles on roads and for measuring inter-vehicle distance.