Top > Search of International Patents > NONLINEAR OPTIMIZATION PROGRAM OF CONTINUOUS VALUE OPTIMIZATION PROBLEM, ROUTE SEARCH PROGRAM, AND ROUTE SEARCH APPARATUS

NONLINEAR OPTIMIZATION PROGRAM OF CONTINUOUS VALUE OPTIMIZATION PROBLEM, ROUTE SEARCH PROGRAM, AND ROUTE SEARCH APPARATUS

Foreign code F180009610
File No. 5529
Posted date Nov 19, 2018
Country WIPO
International application number 2017JP032850
International publication number WO 2018100836
Date of international filing Sep 12, 2017
Date of international publication Jun 7, 2018
Priority data
  • P2016-231278 (Nov 29, 2016) JP
Title NONLINEAR OPTIMIZATION PROGRAM OF CONTINUOUS VALUE OPTIMIZATION PROBLEM, ROUTE SEARCH PROGRAM, AND ROUTE SEARCH APPARATUS
Abstract This search program prepares a variable of an evaluation function separated so as to be independent from a variable of an equality constraint when a Lagrange multiplier method with the equality constraint is applied by using a Lagrange constant for the evaluation function, and carries out a process by using an additional equation constraint that matches the variable of the evaluation function with the variable of the equality constraint. This search program causes an optimization apparatus (1) to alternately repeat a procedure for updating the variable of the evaluation function so as to gradually become close to the equality constraint while searching for a condition at which the evaluation function becomes close to an extreme value and a procedure for updating the variable of the equality constraint so as to gradually become close to the condition at which the evaluation function becomes close to the extreme value while keeping the equality constraint satisfied.
Outline of related art and contending technology BACKGROUND ART
In recent years, for example, for the corresponding event of the driving support device has been developed, particularly in order to reduce the driver's burden to a driver has been developed.This type of driving support device when the route search, the position and speed of this path as a function corresponding to the time, in accordance with these position and velocity based on the evaluation function is introduced into the function, the evaluation function of the extreme value (minimum value) to determine the position and velocity satisfying the, can search for an optimal route has been confirmed by the inventors of the present invention.
In addition, technology related to the present invention has been disclosed in Patent Document 1.Patent Document 1 is, the evaluation function and a constraint condition and treated independently of each other, to minimize the evaluation function satisfies the condition for updating the variables of the constraint for separately updating the variables, 2 of these two update processing are executed alternately, and the constrained minimum of the evaluation function is a technique.
Scope of claims (In Japanese)請求の範囲 [請求項1]
 変数(x ,v )に応じた等式制約が付与された評価関数(H({x ,v }))が極値に近接した条件を満たす前記変数または前記評価関数の最適値を導出する最適化問題に係る最適化プログラムであって、
 前記評価関数にラグランジュ定数(λ)を用いて等式制約付きのラグランジュ未定乗数法を適用するときに前記等式制約の変数(x ,v )と独立的に分離した前記評価関数の変数(p ,q )を用意し、前記評価関数の変数と前記等式制約の変数とを一致させる追加等式制約を用いて処理するプログラムであり、
 最適化装置(1)に、
 前記評価関数が極値に近くなる条件を探索しながら等式制約に徐々に近づくように評価関数の変数を更新する手順と、
 前記等式制約を満足したまま前記評価関数が極値に近くなる条件に徐々に近づくように等式制約の変数を更新する手順と、
 を交互に繰り返し実行させる連続値最適化問題の非線形最適化プログラム。

[請求項2]
 前記追加等式制約に近づくように更新する拡張ラグランジュ未定乗数(θ x,θ v)及び前記評価関数の変数と前記等式制約の変数との前記追加等式制約からのずれを検出するための定数(ρ x,ρ v)を用いた拡張ラグランジュ法を適用して算出するものであって、
 前記評価関数の変数及び前記等式制約の変数を更新した後には前記拡張ラグランジュ未定乗数(θ x,θ v)を更新する請求項1記載の連続値最適化問題の非線形最適化プログラム。

[請求項3]
 前記評価関数の変数の極値を導出するときに、
 前記極値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む全ての変数における評価値よりも大きな値を得る条件を満たす2次関数に置換し、当該2次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用いて極値化する請求項2記載の連続値最適化問題の非線形最適化プログラム。

[請求項4]
 位置変数及び速度変数(x ,v )に応じた等式制約が付与された評価関数(H({x ,v }))が極値に近接した条件を満たす前記位置変数に応じた経路を最適経路として探索する経路探索プログラムであって、
 前記評価関数に前記位置変数及び速度変数に応じた等式制約付きのラグランジュ未定乗数法を適用するときに前記等式制約の位置変数及び速度変数(x ,v )と独立的に分離した前記評価関数の一対の変数(p ,q )を用意し、前記評価関数の一対の変数と前記等式制約の位置変数及び速度変数とをそれぞれ一致させる追加等式制約を用いて処理するプログラムであり、
 経路探索装置(1)に、
 前記評価関数が極値に近くなる条件を探索しながら前記等式制約に徐々に近づくように前記評価関数の一対の変数を更新する手順と、
 前記等式制約を満足したまま前記評価関数が極値に近くなる条件に徐々に近づくように前記等式制約の位置変数及び速度変数を更新する手順と、
 前記評価関数の一対の変数を更新する手順と等式制約の位置変数及び速度変数を更新する手順とを繰り返し行い所定の終了条件を満たして得られた前記位置変数に応じた経路を最適経路として探索する手順と、
 を実行させる経路探索プログラム。

[請求項5]
 前記追加等式制約に近づくように更新する拡張ラグランジュ未定乗数(θ x,θ v)及び前記評価関数の一対の変数と前記等式制約の位置変数及び速度変数との前記追加等式制約からのずれを検出するための定数(ρ x,ρ v)を用いた拡張ラグランジュ法を適用して算出するものであって、
 前記評価関数の一対の変数及び前記等式制約の位置変数及び速度変数を更新した後には前記拡張ラグランジュ未定乗数(θ x,θ v)を更新する請求項4記載の経路探索プログラム。

[請求項6]
 前記評価関数の一対の変数を更新するときに当該評価関数の極値を導出するときには、
 前記極値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む全ての変数における評価値よりも大きな値を得る条件を満たす2次関数に置換し、当該2次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用いて極値化する請求項5記載の経路探索プログラム。

[請求項7]
 位置変数及び速度変数(x ,v )に応じた等式制約が付与された評価関数(H({x ,v }))が極値に近接した条件を満たす前記位置変数に応じた経路を最適経路として探索する経路探索装置(1)であって、
 前記評価関数に前記位置変数及び速度変数に応じた等式制約付きのラグランジュ未定乗数法を適用するときに前記等式制約の位置変数及び速度変数(x ,v )と独立的に分離した前記評価関数の一対の変数(p ,q )を用意し、前記評価関数の一対の変数と前記等式制約の位置変数及び速度変数とをそれぞれ一致させる追加等式制約を用いて処理する経路探索装置であり、
 前記評価関数が極値に近くなる条件を探索しながら前記等式制約に徐々に近づくように前記評価関数の一対の変数を更新する評価関数更新部(10)と、
 前記等式制約を満足したまま前記評価関数が極値に近くなる条件に徐々に近づくように前記等式制約の位置変数及び速度変数を更新する等式制約変数更新部(11)と、
 前記評価関数更新部による更新処理と前記等式制約変数更新部による更新処理とを繰り返し行い所定の終了条件を満たして得られた前記位置変数に応じた経路を最適経路として探索する経路探索部(12)と、
 を備える経路探索装置。

[請求項8]
 前記追加等式制約に近づくように更新する拡張ラグランジュ未定乗数(θ x,θ v)及び前記評価関数の一対の変数と前記等式制約の位置変数及び速度変数との前記追加等式制約からのずれを検出するための定数(ρ x,ρ v)を用いた拡張ラグランジュ法を適用して算出するものであって、
 前記評価関数の一対の変数及び前記等式制約の位置変数及び速度変数を更新した後には前記拡張ラグランジュ未定乗数(θ x,θ v)を更新する拡張ラグランジュ未定乗数更新部(2)、をさらに備える請求項7記載の経路探索装置。

[請求項9]
 前記評価関数更新部が、前記評価関数の一対の変数を更新するときに当該評価関数の極値を導出するときには、
 前記極値の解候補を求めた後、当該解候補を代入したときの微分値が当該評価関数の微分値と等しく、且つ、前記解候補を含む探索空間の内の全ての変数における評価値よりも大きな値を得る条件を満たす2次関数に置換し、当該2次関数の極値を次回の値の解候補として繰り返して更新する補助関数法を用いて極値化する極値化部(2)、
 をさらに備える請求項8記載の経路探索装置。

  • Applicant
  • ※All designated countries except for US in the data before July 2012
  • DENSO CORPORATION
  • KYOTO UNIVERSITY
  • Inventor
  • OKADA, Shuntaro
  • TERABE, Masayoshi
  • OHZEKI, Masayuki
IPC(International Patent Classification)
Specified countries National States: AE AG AL AM AO AT AU AZ BA BB BG BH BN BR BW BY BZ CA CH CL CN CO CR CU CZ DE DJ DK DM DO DZ EC EE EG ES FI GB GD GE GH GM GT HN HR HU ID IL IN IR IS JO KE KG KH KN KP KR KW KZ LA LC LK LR LS LU LY MA MD ME MG MK MN MW MX MY MZ NA NG NI NO NZ OM PA PE PG PH PL PT QA RO RS RU RW SA SC SD SE SG SK SL SM ST SV SY TH TJ TM TN TR TT TZ UA UG US UZ VC VN ZA ZM ZW
ARIPO: BW GH GM KE LR LS MW MZ NA RW SD SL SZ TZ UG ZM ZW
EAPO: AM AZ BY KG KZ RU TJ TM
EPO: AL AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HR HU IE IS IT LT LU LV MC MK MT NL NO PL PT RO RS SE SI SK SM TR
OAPI: BF BJ CF CG CI CM GA GN GQ GW KM ML MR NE SN ST TD TG
Please contact us by e-mail or facsimile if you have any interests on this patent. Thanks.

PAGE TOP

close
close
close
close
close
close