Top > Search of Japanese Patents > NONLINEAR OPTIMIZATION PROGRAM FOR CONTINUOUS VALUE OPTIMIZATION PROBLEM, AND ROUTE SEARCH PROGRAM AND ROUTE SEARCH DEVICE

NONLINEAR OPTIMIZATION PROGRAM FOR CONTINUOUS VALUE OPTIMIZATION PROBLEM, AND ROUTE SEARCH PROGRAM AND ROUTE SEARCH DEVICE UPDATE_EN foreign

Patent code P180015614
File No. 5529
Posted date Nov 22, 2018
Application number P2016-231278
Publication number P2018-087753A
Patent number P6603197
Date of filing Nov 29, 2016
Date of publication of application Jun 7, 2018
Date of registration Oct 18, 2019
Inventor
  • (In Japanese)岡田 俊太郎
  • (In Japanese)寺部 雅能
  • (In Japanese)大関 真之
Applicant
  • (In Japanese)株式会社デンソー
  • (In Japanese)国立大学法人京都大学
Title NONLINEAR OPTIMIZATION PROGRAM FOR CONTINUOUS VALUE OPTIMIZATION PROBLEM, AND ROUTE SEARCH PROGRAM AND ROUTE SEARCH DEVICE UPDATE_EN foreign
Abstract PROBLEM TO BE SOLVED: To provide a nonlinear optimization program for a continuous value optimization problem that is enabled to perform high-speed processing on optimization control, and a route search program and a route search device.
SOLUTION: A search program is adapted to: prepare a variable of an evaluation function independently separated from a variable of equality constraint in applying a Lagrange undetermined multiplier method with the equality constraint using a Lagrange constant for the evaluation function; and perform processing using additional equality constraint for equalizing the variable of the evaluation function to the variable of the equality constraint. With this search program, an optimization device is made to alternately and repeatedly execute: a procedure for updating the variable of the evaluation function so as to gradually approximate the equality constraint while searching for a condition under which the evaluation function becomes closer to an extremal value; and a procedure for updating the variable of the equality constraint to gradually approximate the condition under which the evaluation function comes closer to the extremal value while the equality constraint is satisfied.
Outline of related art and contending technology (In Japanese)

近年、例えば、運転支援装置が事故防止対応のために開発されており、特にドライバーへの運転負担を軽減するために開発されている。この種の運転支援装置が経路探索するときには、この経路の位置及び速度を時間に応じた関数とし、これらの位置及び速度に応じた関数に基づく評価関数を導入し、この評価関数の極値(例えば最小値)を満たす位置及び速度を求めることで、最適な経路を探索できることが発明者らにより確認されている。

なお、本願に関連する技術が特許文献1に開示されている。この特許文献1には、評価関数と制約条件とを独立に扱い、評価関数を極小化するための変数更新処理と制約条件を満足させるための変数更新処理とを分け、これらの2つの更新処理を交互に実行することにより、制約条件付きの評価関数を極小化する技術が開示されている。

Field of industrial application (In Japanese)

本発明は、連続値最適化問題の非線形最適化プログラム、経路探索プログラム、及び経路探索装置に関する。

Scope of claims (In Japanese)
【請求項1】
 
変数(x,v)に応じた等式制約が付与された評価関数(H({x,v}))が極値に近接した条件を満たす前記変数または前記評価関数の最適値を導出する最適化問題に係る最適化プログラムであって、
前記評価関数にラグランジュ定数(λ)を用いて等式制約付きのラグランジュ未定乗数法を適用するときに前記等式制約の変数(x,v)と独立的に分離した前記評価関数の変数(p,q)を用意し、前記評価関数の変数と前記等式制約の変数とを一致させる追加等式制約を用いて処理するプログラムであり、
最適化装置(1)に、
前記評価関数が極値に近くなる条件を探索しながら等式制約に徐々に近づくように評価関数の変数を更新する手順と、
前記等式制約を満足したまま前記評価関数が極値に近くなる条件に徐々に近づくように等式制約の変数を更新する手順と、
を交互に繰り返し実行させる連続値最適化問題の非線形最適化プログラム。

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

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

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

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

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

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

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

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

※Click image to enlarge.

JP2016231278thum.jpg
State of application right Registered
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
close