論文の概要: A binarized-domains arc-consistency algorithm for TCSPs: its computational analysis and its use as a filtering procedure in solution search algorithms

• arxiv url: http://arxiv.org/abs/2002.11508v2
• Date: Fri, 2 Apr 2021 16:40:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 19:28:07.294082
• Title: A binarized-domains arc-consistency algorithm for TCSPs: its computational analysis and its use as a filtering procedure in solution search algorithms
• Title（参考訳）: tcspsのための2値化ドメインアーク一貫性アルゴリズム:その計算解析と解探索アルゴリズムにおけるフィルタリング手順としての利用
• Authors: Amar Isli
• Abstract要約: TCSP(Temporal Constraint Satisfaction Problems)は、制約を二項化することで一意的な制約を取り除く。 我々は,TSPの弧整合性の概念を定義し,これを二項化領域Arc整合性と呼ぶ。 我々は、一般のTCSPソルバと、TCSPベースのジョブショップスケジューラの両方で結果の使い方を示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: TCSPs (Temporal Constraint Satisfaction Problems), as defined in [Dechter et al., 1991], get rid of unary constraints by binarizing them after having added an "origin of the world" variable. In this work, we look at the constraints between the "origin of the world" variable and the other variables, as the (binarized) domains of these other variables. With this in mind, we define a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains Arc-Consistency, or bdArc-Consistency for short. We provide an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as bdAC-3, for it is an adaptation of Mackworth's [1977] well-known arc-consistency algorithm AC-3. We show that if a convex TCSP, referred to in [Dechter et al., 1991] as an STP (Simple Temporal Problem), is bdArc-Consistent, and its "origin of the world" variable disconnected from none of the other variables, its binarized domains are minimal. We provide two polynomial backtrack-free procedures: one for the task of getting, from a bdArc-Consistent STP, either that it is inconsistent or, in case of consistency, a bdArc-Consistent STP refinement whose "origin of the world" variable is disconnected from none of the other variables; the other for the task of getting a solution from a bdArc-Consistent STP whose "origin of the world" variable is disconnected from none of the other variables. We then show how to use our results both in a general TCSP solver and in a TCSP-based job shop scheduler. From our work can be extracted a one-to-all all-to-one shortest paths algorithm of an IR-labelled directed graph. Finally, we show that an existing adaptation to TCSPs of Mackworth's [1977] path-consistency algorithm PC-2 is not guaranteed to always terminate, and correct it.
• Abstract（参考訳）: TCSP (Temporal Constraint Satisfaction Problems) は、[Dechter et al., 1991] で定義されている「世界のオリジン」変数を加えて二項化することによって、一項制約を取り除く。 本研究では、これら他の変数の(バイナリ化された)領域として、「世界のオリジン」変数と他の変数の間の制約を考察する。 これを念頭に置いて、tcspsのarc-consistencyの概念を定義し、これをbinarized-domains arc-consistency、略してbdarc-consistencyと呼ぶ。 マックワースの[1977]よく知られたアークコンシスタンスアルゴリズムac-3の適応であるので、bdac-3と呼ぶtcspのbdarcコンシスタンスを達成するアルゴリズムを提供する。 我々は,[Dechter et al., 1991] で STP (Simple Temporal Problem) として言及された凸 TCSP が bdArc-Consistent であり,その「世界のオリジン」変数が他の変数から切り離された場合,その二項化領域は最小となることを示す。 1つはbdArc-Consistent STPから取得するタスク、もう1つはbdArc-Consistent STPの不整合である、または、一貫性の場合には「世界のオリジン」変数が他の変数から切り離されたbdArc-Consistent STP精細化、もう1つは「世界のオリジン」変数が他の変数から切り離されたbdArc-Consistent STPから解を得るタスクである。 次に、一般的なTCSPソルバと、TCSPベースのジョブショップスケジューラの両方で結果の使い方を示す。 我々の研究から、IR標識付き有向グラフの1対1のショートパスアルゴリズムを抽出することができる。 最後に, Mackworth の[1977] パス一貫性アルゴリズムである PC-2 の TCSP への適応が常に終了することが保証されていないことを示す。

関連論文リスト

• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Switch and Conquer: Efficient Algorithms By Switching Stochastic Gradient Oracles For Decentralized Saddle Point Problems [1.2277343096128712]
  そこで本研究では, 一次変数と双対変数の更新を可能にする非接触な原始的ハイブリッド勾配(非接触PDHG)法を開発した。 GSGとSVRGの最適収束位相を利用することで、C-DPSSGが低-ナトリウム精度の解を得るのに適していることを示す。
  論文  参考訳（メタデータ） (2023-09-02T17:48:42Z)
• Convergence of policy gradient methods for finite-horizon exploratory linear-quadratic control problems [3.8661825615213012]
  有限水平連続時間探索線形四元数制御(LQC)問題に対する政策勾配法(PG法)の大域的線形収束について検討する。 本稿では,離散時間ポリシーを持つ新しいPG法を提案する。このアルゴリズムは連続時間解析を活用し,動作周波数の異なる線形収束性を実現する。
  論文  参考訳（メタデータ） (2022-11-01T17:31:41Z)
• Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning [82.31436758872715]
  我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。 値関数と有限水平マルコフ決定過程の接続を確立する。
  論文  参考訳（メタデータ） (2021-11-01T00:21:24Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• ADOM: Accelerated Decentralized Optimization Method for Time-Varying Networks [124.33353902111939]
  本稿では,時間変動ネットワーク上の滑らかかつ強凸分散最適化のための高速化手法である adom を提案する。 ネットワーク構造のみに依存する一定の要因まで、その通信は加速されたNesterovメソッドのそれと同じです。
  論文  参考訳（メタデータ） (2021-02-18T09:37:20Z)
• Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysis [27.679514676804057]
  オフ・ポリシー・セッティングにおける2つの時間スケールTDCアルゴリズムの分散化手法を開発した。 実験により,提案した分散還元型TDCは,従来のTDCと分散還元型TDよりも収束誤差が小さいことを示した。
  論文  参考訳（メタデータ） (2020-10-26T01:33:05Z)
• Smooth Deformation Field-based Mismatch Removal in Real-time [10.181846237133167]
  非剛性変形は、パラメトリック変換が見つからないため、ミスマッチの除去を困難にする。 再重み付けと1点RANSAC戦略(R1P-RNSC)に基づくアルゴリズムを提案する。 両アルゴリズムの組み合わせは,他の最先端手法と比較して精度が高いことを示す。
  論文  参考訳（メタデータ） (2020-07-16T18:20:25Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  本稿では,勾配降下(SGD)の軌跡を解析する。 我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
  論文  参考訳（メタデータ） (2020-06-19T14:11:26Z)
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms [58.57004511121862]
  アクタークリティカル(AC)とナチュラルアクタークリティカル(NAC)のアルゴリズムは、最適なポリシーを見つけるために2つの方法で実行されることが多い。 2つの時間スケールACは、$mathcalO(epsilon-2.5log3(epsilon-1))$で、$epsilon$-accurateの定常点に達するために、全体のサンプルの複雑さを必要とすることを示す。 我々は,動的にマルコフサンプリングが変化するため,アクターのバイアス誤差をバウンドする新しい手法を開発した。
  論文  参考訳（メタデータ） (2020-05-07T15:42:31Z)
• TEASER: Fast and Certifiable Point Cloud Registration [30.19476775410544]
  最初の高速かつ堅牢な3Dポイントの登録アルゴリズムは、大量の外れ値の存在下での3Dポイントの登録である。 TEASER++という名前の第二の高速で堅牢な認証翻訳は、大規模なサブプロブレムを解決するために、既成の非コンポーネントを使用する。
  論文  参考訳（メタデータ） (2020-01-21T18:56:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。