Graphical Model Inference in Optimal Control of Stochastic Multi-Agent Systems
確率的マルチエージェントシステムの最適制御におけるグラフィカルモデル推論
In this article we consider the issue of optimal control in collaborative multi-agent systems with stochastic dynamics. The agents have a joint task in which they have to reach a number of target states. The dynamics of the agents contains additive control and additive noise, and the autonomous part factorizes over the agents. Full observation of the global state is assumed. The goal is to minimize the accumulated joint cost, which consists of integrated instantaneous costs and a joint end cost. The joint end cost expresses the joint task of the agents. The instantaneous costs are quadratic in the control and factorize over the agents. The optimal control is given as a weighted linear combination of single-agent to single-target controls. The single-agent to single-target controls are expressed in terms of diffusion processes. These controls, when not closed form expressions, are formulated in terms of path integrals, which are calculated approximately by Metropolis-Hastings sampling. The weights in the control are interpreted as marginals of a joint distribution over agent to target assignments. The structure of the latter is represented by a graphical model, and the marginals are obtained by graphical model inference. Exact inference of the graphical model will break down in large systems, and so approximate inference methods are needed. We use naive mean field approximation and belief propagation to approximate the optimal control in systems with linear dynamics. We compare the approximate inference methods with the exact solution, and we show that they can accurately compute the optimal control. Finally, we demonstrate the control method in multi-agent systems with nonlinear dynamics consisting of up to 80 agents that have to reach an equal number of target states.
本稿では、確率ダイナミクスを有する協調型マルチエージェントシステムにおける最適制御の問題を検討します。エージェントは、複数の目標状態に到達するという共同タスクを持つ。エージェントのダイナミクスには加法的な制御と加法的なノイズが含まれ、自律部分はエージェント間で因数分解されます。全体状態は完全に観測されることが前提となります。目標は、累積された同時コストを最小化することです。これは、統合された瞬間コストと同時終了コストから構成されます。同時終了コストは、エージェントの同時タスクを表します。瞬間コストは制御において2次式であり、エージェント間で因数分解されます。最適制御は、単一エージェントから単一ターゲットへの制御の重み付き線形結合として与えられます。単一エージェントから単一ターゲットへの制御は、拡散過程によって表現されます。これらの制御は、閉形式表現でない場合、メトロポリス・ヘイスティングス・サンプリングによって近似的に計算される経路積分によって定式化されます。制御における重みは、エージェントからターゲットへの割り当てにおける同時分布の周辺分布として解釈されます。後者の構造はグラフィカルモデルによって表現され、周辺分布はグラフィカルモデル推論によって得られます。グラフィカルモデルの正確な推論は大規模システムでは破綻するため、近似推論手法が必要となります。線形ダイナミクスを持つシステムにおける最適制御を近似するために、ナイーブ平均場近似とビリーフプロパゲーションを使用します。近似推論法と厳密解を比較し、それらが最適制御を正確に計算できることを示します。最後に、最大80のエージェントからなる非線形ダイナミクスを持つマルチエージェントシステムにおいて、同数の目標状態に到達しなければならない制御法を示します。
Optimal Strategies for Simultaneous Vickrey Auctions with Perfect Substitutes
完全代替物を用いた同時ヴィックレイオークションの最適戦略
We derive optimal strategies for a bidding agent that participates in multiple, simultaneous second-price auctions with perfect substitutes. We prove that, if everyone else bids locally in a single auction, the global bidder should always place non-zero bids in all available auctions, provided there are no budget constraints. With a budget, however, the optimal strategy is to bid locally if this budget is equal or less than the valuation. Furthermore, for a wide range of valuation distributions, we prove that the problem of finding the optimal bids reduces to two dimensions if all auctions are identical. Finally, we address markets with both sequential and simultaneous auctions, non-identical auctions, and the allocative efficiency of the market.
我々は、完全代替品を用いた複数の同時第2価格オークションに参加する入札エージェントの最適戦略を導出します。予算制約がない場合、他の全員が単一のオークションで局所的に入札する場合、全体入札者は利用可能なすべてのオークションにおいて常に非ゼロ入札を行うべきであることを証明します。しかし、予算がある場合、最適戦略は、この予算が評価額以下の場合、局所的に入札することです。さらに、様々な評価額分布において、すべてのオークションが同一であれば、最適入札を求める問題は2次元に簡約されることを証明します。最後に、逐次オークションと同時オークションの両方、非同一オークション、そして市場の配分効率性について考察します。
The Ultrametric Constraint and its Application to Phylogenetics
超計量制約とその系統発生学への応用
A phylogenetic tree shows the evolutionary relationships among species. Internal nodes of the tree represent speciation events and leaf nodes correspond to species. A goal of phylogenetics is to combine such trees into larger trees, called supertrees, whilst respecting the relationships in the original trees. A rooted tree exhibits an ultrametric property; that is, for any three leaves of the tree it must be that one pair has a deeper most recent common ancestor than the other pairs, or that all three have the same most recent common ancestor. This inspires a constraint programming encoding for rooted trees. We present an efficient constraint that enforces the ultrametric property over a symmetric array of constrained integer variables, with the inevitable property that the lower bounds of any three variables are mutually supportive. We show that this allows an efficient constraint-based solution to the supertree construction problem. We demonstrate that the versatility of constraint programming can be exploited to allow solutions to variants of the supertree construction problem.
系統樹は、種間の進化的関係を示す。系統樹の内部ノードは種分化イベントを表し、葉ノードは種に対応します。系統学の目標は、このような系統樹を、元の系統樹の関係性を尊重しつつ、スーパーツリーと呼ばれるより大きな系統樹に統合することです。根付き系統樹は超計量的性質を示す。つまり、系統樹の任意の3つの葉について、1つのペアが他のペアよりも深い直近の共通祖先を持つか、3つすべてが同じ直近の共通祖先を持つかのいずれかです。これは、根付き系統樹のための制約プログラミングのエンコーディングに着想を与える。本稿では、制約付き整数変数の対称配列に対して超計量的性質を強制する効率的な制約を提示します。この制約は、任意の3つの変数の下限が互いに支持的であるという必然的な性質を持つ。これにより、スーパーツリー構築問題に対する効率的な制約ベースの解が得られることを示す。制約プログラミングの汎用性を活用することで、スーパーツリー構築問題の様々なバリエーションに対する解が得られることを示す。
Latent Tree Models and Approximate Inference in Bayesian Networks
ベイジアンネットワークにおける潜在木モデルと近似推論
We propose a novel method for approximate inference in Bayesian networks (BNs). The idea is to sample data from a BN, learn a latent tree model (LTM) from the data offline, and when online, make inference with the LTM instead of the original BN. Because LTMs are tree-structured, inference takes linear time. In the meantime, they can represent complex relationship among leaf nodes and hence the approximation accuracy is often good. Empirical evidence shows that our method can achieve good approximation accuracy at low online computational cost.
我々は、ベイジアンネットワーク（BN）における近似推論のための新しい手法を提案します。そのアイデアは、BNからデータをサンプリングし、オフラインでデータから潜在木モデル（LTM）を学習し、オンライン時には元のBNではなくLTMを用いて推論を行うというものです。LTMは木構造であるため、推論には線形時間がかかる。一方で、LTMは葉ノード間の複雑な関係を表現できるため、近似精度は多くの場合良好です。経験的証拠は、私たちの方法が低いオンライン計算コストで優れた近似精度を達成できることを示しています。
Qualitative System Identification from Imperfect Data
不完全データからの定性的なシステム同定
Experience in the physical sciences suggests that the only realistic means of understanding complex systems is through the use of mathematical models. Typically, this has come to mean the identification of quantitative models expressed as differential equations. Quantitative modelling works best when the structure of the model (i.e., the form of the equations) is known; and the primary concern is one of estimating the values of the parameters in the model. For complex biological systems, the model-structure is rarely known and the modeler has to deal with both model-identification and parameter-estimation. In this paper we are concerned with providing automated assistance to the first of these problems. Specifically, we examine the identification by machine of the structural relationships between experimentally observed variables. These relationship will be expressed in the form of qualitative abstractions of a quantitative model. Such qualitative models may not only provide clues to the precise quantitative model, but also assist in understanding the essence of that model. Our position in this paper is that background knowledge incorporating system modelling principles can be used to constrain effectively the set of good qualitative models. Utilising the model-identification framework provided by Inductive Logic Programming (ILP) we present empirical support for this position using a series of increasingly complex artificial datasets. The results are obtained with qualitative and quantitative data subject to varying amounts of noise and different degrees of sparsity. The results also point to the presence of a set of qualitative states, which we term kernel subsets, that may be necessary for a qualitative model-learner to learn correct models. We demonstrate scalability of the method to biological system modelling by identification of the glycolysis metabolic pathway from data.
物理科学における経験から、複雑系を理解する唯一の現実的な手段は数理モデルを用いることであることが示唆されています。典型的には、これは微分方程式として表現される定量的モデルの同定を意味するようになった。定量的モデリングは、モデルの構造（すなわち方程式の形式）が既知である場合に最も効果的に機能し、主要な関心事はモデル内のパラメータ値を推定することです。複雑な生物系の場合、モデル構造が既知であることは稀であり、モデラーはモデルの同定とパラメータ推定の両方に取り組まなければならない。本稿では、これらの問題のうち前者に対する自動支援を提供することを目的とします。具体的には、実験的に観測された変数間の構造的関係を機械が同定する方法について検討します。これらの関係は、定量的モデルを定性的に抽象化した形で表現されます。このような定性モデルは、正確な定量的モデルへの手がかりを提供するだけでなく、そのモデルの本質を理解する上でも役立つ可能性があります。本稿における我々の立場は、システムモデリングの原則を組み込んだ背景知識を用いることで、優れた定性モデル群を効果的に絞り込むことができるというものです。帰納的論理プログラミング（ILP）によって提供されるモデル識別フレームワークを活用し、我々は一連の複雑化する人工データセットを用いて、この立場を実証的に裏付ける。結果は、様々な量のノイズと様々な程度のスパース性を伴う定性的および定量的データを用いて得られた。また、定性的モデル学習者が正しいモデルを学習するために必要となる可能性のある、カーネルサブセットと呼ぶ一連の定性状態の存在も示唆しています。我々は、データから解糖代謝経路を識別することで、この手法が生物システムモデリングに拡張可能であることを実証します。
Analogical Dissimilarity: Definition, Algorithms and Two Experiments in Machine Learning
類推的非類似性：定義、アルゴリズム、そして機械学習における2つの実験
This paper defines the notion of analogical dissimilarity between four objects, with a special focus on objects structured as sequences. Firstly, it studies the case where the four objects have a null analogical dissimilarity, i.e. are in analogical proportion. Secondly, when one of these objects is unknown, it gives algorithms to compute it. Thirdly, it tackles the problem of defining analogical dissimilarity, which is a measure of how far four objects are from being in analogical proportion. In particular, when objects are sequences, it gives a definition and an algorithm based on an optimal alignment of the four sequences. It gives also learning algorithms, i.e. methods to find the triple of objects in a learning sample which has the least analogical dissimilarity with a given object. Two practical experiments are described: the first is a classification problem on benchmarks of binary and nominal data, the second shows how the generation of sequences by solving analogical equations enables a handwritten character recognition system to rapidly be adapted to a new writer.
本論文では、4つのオブジェクト間の類似性の違いの概念を定義し、特にシーケンスとして構造化されたオブジェクトに焦点を当てます。まず、4つのオブジェクトの類似性の違いがゼロの場合、つまり類似比例関係にある場合を考察します。次に、これらのオブジェクトの1つが不明な場合、それを計算するアルゴリズムを提示します。最後に、4つのオブジェクトが類似比例関係にあることからどれだけ離れているかを示す尺度である類似性の違いの定義問題に取り組みます。特に、オブジェクトがシーケンスである場合、4つのシーケンスの最適な配置に基づく定義とアルゴリズムを提示します。また、学習アルゴリズム、すなわち、学習サンプルにおいて、与えられたオブジェクトとの類似性の違いが最も小さい3つのオブジェクトを見つける手法も提示します。2つの実用的な実験について説明します。1つ目は、2値データと名目データのベンチマークにおける分類問題です。2つ目は、類似方程式を解くことでシーケンスを生成することで、手書き文字認識システムを初心者に迅速に適応させる方法を示します。
Compositional Belief Update
構成的信念更新
In this paper we explore a class of belief update operators, in which the definition of the operator is compositional with respect to the sentence to be added. The goal is to provide an update operator that is intuitive, in that its definition is based on a recursive decomposition of the update sentence’s structure, and that may be reasonably implemented. In addressing update, we first provide a definition phrased in terms of the models of a knowledge base. While this operator satisfies a core group of the benchmark Katsuno-Mendelzon update postulates, not all of the postulates are satisfied. Other Katsuno-Mendelzon postulates can be obtained by suitably restricting the syntactic form of the sentence for update, as we show. In restricting the syntactic form of the sentence for update, we also obtain a hierarchy of update operators with Winslett’s standard semantics as the most basic interesting approach captured. We subsequently give an algorithm which captures this approach; in the general case the algorithm is exponential, but with some not-unreasonable assumptions we obtain an algorithm that is linear in the size of the knowledge base. Hence the resulting approach has much better complexity characteristics than other operators in some situations. We also explore other compositional belief change operators: erasure is developed as a dual operator to update; we show that a forget operator is definable in terms of update; and we give a definition of the compositional revision operator. We obtain that compositional revision, under the most natural definition, yields the Satoh revision operator.
本稿では、追加される文に関して構成的な定義を持つ信念更新演算子のクラスを検討します。目標は、更新文の構造の再帰分解に基づいて定義されるという点で直感的で、かつ合理的に実装可能な更新演算子を提供することです。更新を扱うにあたり、まず知識ベースのモデルを用いて定義します。この演算子は、ベンチマークとなるKatsuno-Mendelzon更新公理の中核グループを満たしているが、すべての公理が満たされているわけではない。他のKatsuno-Mendelzon公理は、以下に示すように、更新の文の統語形式を適切に制限することで得られます。更新のために文の統語形式を制限することで、最も基本的で興味深いアプローチであるウィンスレットの標準意味論による更新演算子の階層も得られます。次に、このアプローチを捉えるアルゴリズムを示します。一般的なケースではアルゴリズムは指数関数的ですが、いくつかの不合理ではない仮定を置くことで、知識ベースのサイズに線形なアルゴリズムが得られます。したがって、結果として得られるアプローチは、状況によっては他の演算子よりもはるかに優れた計算特性を持ちます。また、他の構成的信念変更演算子についても検討します。消去は更新のデュアル演算子として開発され、忘却演算子は更新に関して定義可能であることを示します。そして、構成的修正演算子の定義を示します。最も自然な定義による構成的修正は、佐藤修正演算子を生成することがわかります。
M-DPOP: Faithful Distributed Implementation of Efficient Social Choice Problems
M-DPOP: 効率的な社会選択問題の忠実な分散実装
In the efficient social choice problem, the goal is to assign values, subject to side constraints, to a set of variables to maximize the total utility across a population of agents, where each agent has private information about its utility function. In this paper we model the social choice problem as a distributed constraint optimization problem (DCOP), in which each agent can communicate with other agents that share an interest in one or more variables. Whereas existing DCOP algorithms can be easily manipulated by an agent, either by misreporting private information or deviating from the algorithm, we introduce M-DPOP, the first DCOP algorithm that provides a faithful distributed implementation for efficient social choice. This provides a concrete example of how the methods of mechanism design can be unified with those of distributed optimization. Faithfulness ensures that no agent can benefit by unilaterally deviating from any aspect of the protocol, neither information-revelation, computation, nor communication, and whatever the private information of other agents. We allow for payments by agents to a central bank, which is the only central authoritythat we require. To achieve faithfulness, we carefully integrate the Vickrey-Clarke-Groves (VCG) mechanism with the DPOP algorithm, such that each agent is only asked to perform computation, report information, and send messages that is in its own best interest. Determining agent i’s payment requires solving the social choice problem without agent i. Here, we present a method to reuse computation performed in solving the main problem in a way that is robust against manipulation by the excluded agent. Experimental results on structured problems show that as much as 87% of the computation required for solving the marginal problems can be avoided by re-use, providing very good scalability in the number of agents.On unstructured problems, we observe a sensitivity of M-DPOP to the density of the problem, and we show that reusability decreases from almost 100% for very sparse problems to around 20% for highly connected problems. We close with a discussion of the features of DCOP that enable faithful implementations in this problem, the challenge of reusing computation from the main problem to marginal problems in other algorithms such as ADOPT and OptAPO, and the prospect of methods to avoid the welfare loss that can occur because of the transfer of payments to the bank.
効率的な社会選択問題における目標は、各エージェントが自身の効用関数に関する秘密情報を持つエージェント集団全体の効用を最大化するために、変数の集合に副次的な制約を課す値を割り当てることです。本稿では、社会選択問題を分散制約最適化問題（DCOP）としてモデル化します。DCOPでは、各エージェントは1つ以上の変数に関心を共有する他のエージェントと通信できます。既存のDCOPアルゴリズムは、エージェントが秘密情報を誤って報告したり、アルゴリズムから逸脱したりすることで容易に操作される可能性があります。そこで本稿では、効率的な社会選択のための忠実な分散実装を提供する最初のDCOPアルゴリズムであるM-DPOPを紹介します。これは、メカニズム設計の手法と分散最適化の手法をどのように統合できるかを示す具体的な例です。忠実性は、どのエージェントも、プロトコルのいかなる側面（情報の開示、計算、通信、そして他のエージェントの秘密情報）からも一方的に逸脱することで利益を得ることができないことを保証します。本稿で唯一必要な中央機関である中央銀行へのエージェントによる支払いを許容します。忠実性を実現するために、各エージェントが自身の最善の利益になる計算、情報の報告、メッセージの送信のみを行うように、Vickrey-Clarke-Groves (VCG)メカニズムをDPOPアルゴリズムに慎重に統合します。エージェントiの支払いを決定するには、エージェントiなしで社会的選択問題を解決する必要があります。ここでは、除外されたエージェントによる操作に対して堅牢な方法で、主要な問題を解決するために実行された計算を再利用する手法を紹介します。構造化問題での実験結果によると、限界問題を解決するために必要な計算の最大87%を再利用によって回避でき、エージェントの数に関して非常に優れたスケーラビリティが得られます。非構造化問題では、M-DPOPが問題の密度に敏感であることがわかり、非常に疎な問題では再利用性がほぼ100%ですが、高度に接続された問題では約20%に低下することがわかります。最後に、この問題における忠実な実装を可能にするDCOPの特徴、ADOPTやOptAPOといった他のアルゴリズムにおける主問題から周辺問題への計算再利用の課題、そして銀行への支払い移転によって生じる可能性のある福祉損失を回避する方法の見通しについて議論します。
Online Planning Algorithms for POMDPs
POMDPのためのオンラインプランニングアルゴリズム
Partially Observable Markov Decision Processes (POMDPs) provide a rich framework for sequential decision-making under uncertainty in stochastic domains. However, solving a POMDP is often intractable except for small problems due to their complexity. Here, we focus on online approaches that alleviate the computational complexity by computing good local policies at each decision step during the execution. Online algorithms generally consist of a lookahead search to find the best action to execute at each time step in an environment. Our objectives here are to survey the various existing online POMDP methods, analyze their properties and discuss their advantages and disadvantages; and to thoroughly evaluate these online approaches in different environments under various metrics (return, error bound reduction, lower bound improvement). Our experimental results indicate that state-of-the-art online heuristic search methods can handle large POMDP domains efficiently.
部分観測マルコフ決定過程（POMDP）は、確率領域における不確実性の下での逐次的意思決定のための優れた枠組みを提供します。しかし、POMDPの解法は、その複雑さゆえに、小さな問題を除いてしばしば扱いにくい。ここでは、実行中の各決定ステップにおいて適切なローカルポリシーを計算することで計算の複雑さを軽減するオンライン手法に焦点を当てます。オンラインアルゴリズムは一般的に、環境内の各タイムステップで実行する最適なアクションを見つけるための先読み探索で構成されます。ここでの目的は、既存の様々なオンラインPOMDP手法を調査し、その特性を分析し、長所と短所を議論することです。そして、様々な環境において、様々な指標（リターン、誤差限界の削減、下限の改善）に基づいてこれらのオンライン手法を徹底的に評価します。実験結果は、最先端のオンラインヒューリスティック探索手法が大規模なPOMDPドメインを効率的に処理できることを示しています。
A General Theory of Additive State Space Abstractions
加法的な状態空間抽象化の一般理論
Informally, a set of abstractions of a state space S is additive if the distance between any two states in S is always greater than or equal to the sum of the corresponding distances in the abstract spaces. The first known additive abstractions, called disjoint pattern databases, were experimentally demonstrated to produce state of the art performance on certain state spaces. However, previous applications were restricted to state spaces with special properties, which precludes disjoint pattern databases from being defined for several commonly used testbeds, such as Rubik’s Cube, TopSpin and the Pancake puzzle. In this paper we give a general definition of additive abstractions that can be applied to any state space and prove that heuristics based on additive abstractions are consistent as well as admissible. We use this new definition to create additive abstractions for these testbeds and show experimentally that well chosen additive abstractions can reduce search time substantially for the (18,4)-TopSpin puzzle and by three orders of magnitude over state of the art methods for the 17-Pancake puzzle. We also derive a way of testing if the heuristic value returned by additive abstractions is provably too low and show that the use of this test can reduce search time for the 15-puzzle and TopSpin by roughly a factor of two.
非公式には、状態空間Sの抽象化の集合は、S内の任意の2つの状態間の距離が、抽象空間内の対応する距離の合計以上である場合に加法的です。最初に知られた加法的抽象化は、分離パターンデータベースと呼ばれ、特定の状態空間で最先端のパフォーマンスを生み出すことが実験的に実証されました。しかし、これまでの応用は特殊な特性を持つ状態空間に限定されており、ルービックキューブ、トップスピン、パンケーキパズルなど、一般的に使用されるいくつかのテストベッドに対して分離パターンデータベースを定義することができませんでした。本稿では、任意の状態空間に適用可能な加法的抽象化の一般的な定義を示し、加法的抽象化に基づくヒューリスティックが一貫性と許容性を持つことを証明します。この新しい定義を用いて、これらのテストベッド用の加法的抽象化を作成し、適切に選択された加法的抽象化によって、(18,4)-TopSpinパズルの探索時間が大幅に短縮され、17-Pancakeパズルの探索時間も最先端手法に比べて3桁短縮されることを実験的に示す。また、加法的抽象化によって返されるヒューリスティック値が低すぎるかどうかをテストする方法を導出し、このテストを用いることで、15-PancakeパズルとTopSpinの探索時間を約2分の1に短縮できることを示す。
A Unifying Framework for Structural Properties of CSPs: Definitions, Complexity, Tractability
CSPの構造的特性の統一的枠組み：定義、複雑性、扱いやすさ
Literature on Constraint Satisfaction exhibits the definition of several “structural” properties that can be possessed by CSPs, like (in)consistency, substitutability or interchangeability.Current tools for constraint solving typically detect such properties efficiently by means of incomplete yet effective algorithms, and use them to reduce the search space and boost search.In this paper, we provide a unifying framework encompassing most of the properties known so far, both in CSP and other fields’ literature, and shed light on the semantical relationships among them.This gives a unified and comprehensive view of the topic, allows new, unknown, properties to emerge, and clarifies the computational complexity of the various detection problems.In particular, among the others, two new concepts, fixability and removability emerge, that come out to be the ideal characterisations of values that may be safely assigned or removed from a variable’s domain, while preserving problem satisfiability. These two notions subsume a large number of known properties, includinginconsistency, substitutability and others.Because of the computational intractability of all the property-detection problems, by following the CSP approach we then determine a number of relaxations which provide sufficient conditions for their tractability. In particular, we exploit forms of language restrictions and local reasoning.
制約充足に関する文献には、一貫性(非一貫性)、代替可能性、互換性など、CSPが持つことができるいくつかの「構造的」プロパティの定義が示されています。制約を解決するための現在のツールは、通常、不完全ながらも効果的なアルゴリズムを使用してこれらのプロパティを効率的に検出し、それらを使用して検索空間を削減し、検索を強化します。この論文では、CSPと他の分野の文献の両方でこれまでに知られているプロパティのほとんどを網羅する統一フレームワークを提供し、それらの間の意味的関係を明らかにします。これにより、トピックの統一された包括的な視点が得られ、新しい未知のプロパティが出現し、さまざまな検出問題の計算の複雑さが明確になります。特に、他の概念の中でも、問題の充足可能性を維持しながら、変数のドメインに安全に割り当てられるか、または変数のドメインから削除される値の理想的な特徴付けである、固定可能性と削除可能性という2つの新しい概念が浮上します。これら2つの概念は、矛盾性、代替可能性など、多数の既知の特性を包含しています。すべての特性検出問題は計算的に扱いにくいため、CSPアプローチに従うことで、それらの扱いやすさの十分な条件を提供するいくつかの緩和策を決定します。特に、言語制約と局所推論の形式を活用します。
SATzilla: Portfolio-based Algorithm Selection for SAT
SATzilla: SATのためのポートフォリオベースのアルゴリズム選択
It has been widely observed that there is no single “dominant” SAT solver; instead, different solvers perform best on different instances. Rather than following the traditional approach of choosing the best solver for a given class of instances, we advocate making this decision online on a per-instance basis. Building on previous work, we describe SATzilla, an automated approach for constructing per-instance algorithm portfolios for SAT that use so-called empirical hardness models to choose among their constituent solvers. This approach takes as input a distribution of problem instances and a set of component solvers, and constructs a portfolio optimizing a given objective function (such as mean runtime, percent of instances solved, or score in a competition). The excellent performance of SATzilla was independently verified in the 2007 SAT Competition, where our SATzilla07 solvers won three gold, one silver and one bronze medal. In this article, we go well beyond SATzilla07 by making the portfolio construction scalable and completely automated, and improving it by integrating local search solvers as candidate solvers, by predicting performance score instead of runtime, and by using hierarchical hardness models that take into account different types of SAT instances. We demonstrate the effectiveness of these new techniques in extensive experimental results on data sets including instances from the most recent SAT competition.
「支配的な」単一のSATソルバーは存在しないことが広く観察されています。むしろ、異なるインスタンスに対して異なるソルバーが最良のパフォーマンスを発揮します。与えられたインスタンスのクラスに対して最適なソルバーを選択するという従来のアプローチに従うのではなく、我々はインスタンスごとにオンラインでこの決定を行うことを提唱します。これまでの研究に基づき、SATzillaについて説明します。SATzillaは、SATインスタンスごとのアルゴリズムポートフォリオを自動構築する手法で、構成ソルバーの選択にいわゆる経験的困難性モデルを使用します。この手法は、問題インスタンスの分布と構成ソルバーのセットを入力として受け取り、与えられた目的関数（平均実行時間、解決されたインスタンスの割合、競技スコアなど）を最適化するポートフォリオを構築します。SATzillaの優れた性能は、2007年のSATコンペティションで独立して検証され、SATzilla07ソルバーは金メダル3個、銀メダル1個、銅メダル1個を獲得しました。本稿では、ポートフォリオ構築をスケーラブルかつ完全に自動化し、局所探索ソルバーを候補ソルバーとして統合し、実行時間ではなくパフォーマンススコアを予測し、異なるタイプのSATインスタンスを考慮した階層的困難性モデルを使用することで、SATzilla07をはるかに凌駕する性能を実現します。最新のSATコンペティションのインスタンスを含むデータセットを用いた広範な実験結果により、これらの新手法の有効性を実証します。
Efficiency and Envy-freeness in Fair Division of Indivisible Goods: Logical Representation and Complexity
不可分財の公平な分配における効率性と嫉妬のなさ：論理的表現と複雑性
We consider the problem of allocating fairly a set of indivisible goods among agents from the point of view of compact representation and computational complexity. We start by assuming that agents have dichotomous preferences expressed by propositional formulae. We express efficiency and envy-freeness in a logical setting, which reveals unexpected connections to nonmonotonic reasoning. Then we identify the complexity of determining whether there exists an efficient and envy-free allocation, for several notions of efficiency, when preferences are represented in a succinct way (as well as restrictions of this problem). We first study the problem under the assumption that preferences are dichotomous, and then in the general case.
我々は、コンパクトな表現と計算量の観点から、分割不可能な財の集合をエージェント間で公平に割り当てる問題を考察します。まず、エージェントが命題式で表現される二分的な選好を持つと仮定します。効率性と羨望のなさを論理的な設定で表現することで、非単調推論との予期せぬ関連性が明らかになります。次に、選好が簡潔に表現された場合、効率性の概念をいくつか用いて、効率的かつ羨望のない割り当てが存在するかどうかを判断する複雑さ（およびこの問題の制約）を明らかにします。まず、選好が二分的であるという仮定の下で問題を考察し、次に一般の場合について考察します。
Refining the Execution of Abstract Actions with Learned Action Models
学習済み行動モデルを用いた抽象行動実行の洗練
Robots reason about abstract actions, such as “go to position `l'”, in order to decide what to do or to generate plans for their intended course of action. The use of abstract actions enables robots to employ small action libraries, which reduces the search space for decision making. When executing the actions, however, the robot must tailor the abstract actions to the specific task and situation context at hand.In this article we propose a novel robot action execution system that learns success and performance models for possible specializations of abstract actions. At execution time, the robot uses these models to optimize the execution of abstract actions to the respective task contexts. The robot can so use abstract actions for efficient reasoning, without compromising the performance of action execution. We show the impact of our action execution model in three robotic domains and on two kinds of action execution problems: (1) the instantiation of free action parameters to optimize the expected performance of action sequences; (2) the automatic introduction of additional subgoals to make action sequences more reliable.
ロボットは、「位置`l’へ移動する」といった抽象的な行動について推論を行い、何をすべきかを決定したり、意図した行動計画を立てたりします。抽象的な行動を用いることで、ロボットは小規模な行動ライブラリを利用でき、意思決定のための探索空間を縮小することができます。しかし、行動を実行する際には、ロボットは特定のタスクや状況のコンテキストに合わせて抽象的な行動を調整する必要があります。本稿では、抽象行動の可能な特化について成功モデルとパフォーマンスモデルを学習する、新たなロボット行動実行システムを提案します。ロボットは実行時にこれらのモデルを用いて、それぞれのタスクコンテキストに合わせて抽象行動の実行を最適化します。これにより、ロボットは行動実行のパフォーマンスを損なうことなく、抽象的な行動を効率的な推論に活用することができます。本稿では、3つのロボット領域と2種類の行動実行問題における、この行動実行モデルの影響を示します。(1)行動シーケンスの期待パフォーマンスを最適化するための自由行動パラメータのインスタンス化、(2)行動シーケンスの信頼性を高めるための追加サブゴールの自動導入です。
Adaptive Stochastic Resource Control: A Machine Learning Approach
適応型確率的資源制御：機械学習アプローチ
The paper investigates stochastic resource allocation problems with scarce, reusable resources and non-preemtive, time-dependent, interconnected tasks. This approach is a natural generalization of several standard resource management problems, such as scheduling and transportation problems. First, reactive solutions are considered and defined as control policies of suitably reformulated Markov decision processes (MDPs). We argue that this reformulation has several favorable properties, such as it has finite state and action spaces, it is aperiodic, hence all policies are proper and the space of control policies can be safely restricted. Next, approximate dynamic programming (ADP) methods, such as fitted Q-learning, are suggested for computing an efficient control policy. In order to compactly maintain the cost-to-go function, two representations are studied: hash tables and support vector regression (SVR), particularly, nu-SVRs. Several additional improvements, such as the application of limited-lookahead rollout algorithms in the initial phases, action space decomposition, task clustering and distributed sampling are investigated, too. Finally, experimental results on both benchmark and industry-related data are presented.
本稿では、希少で再利用可能なリソースと、非プリエンプティブで時間依存の相互接続されたタスクを伴う確率的リソース割り当て問題を調査します。このアプローチは、スケジューリングや輸送問題など、いくつかの標準的なリソース管理問題の自然な一般化です。まず、適切に再定式化されたマルコフ決定過程（MDP）の制御ポリシーとして、リアクティブソリューションを検討し、定義します。この定式化には、有限な状態空間と行動空間を持ち、非周期的であるためすべてのポリシーが適切であり、制御ポリシー空間を安全に制限できるなど、いくつかの好ましい特性があると主張します。次に、近似Q学習などの近似動的計画法（ADP）が、効率的な制御ポリシーの計算に提案されます。コスト・トゥ・ゴー関数をコンパクトに維持するために、ハッシュテーブルとサポートベクター回帰（SVR）、特にnu-SVRという2つの表現が検討されます。初期段階での限定先読みロールアウトアルゴリズムの適用、行動空間分解、タスククラスタリング、分散サンプリングなど、いくつかの追加的な改善も調査されます。最後に、ベンチマークデータと業界関連データの両方における実験結果を示す。
Dynamic Control in Real-Time Heuristic Search
リアルタイムヒューリスティック探索における動的制御
Real-time heuristic search is a challenging type of agent-centered search because the agent’s planning time per action is bounded by a constant independent of problem size. A common problem that imposes such restrictions is pathfinding in modern computer games where a large number of units must plan their paths simultaneously over large maps. Common search algorithms (e.g., A*, IDA*, D*, ARA*, AD*) are inherently not real-time and may lose completeness when a constant bound is imposed on per-action planning time. Real-time search algorithms retain completeness but frequently produce unacceptably suboptimal solutions. In this paper, we extend classic and modern real-time search algorithms with an automated mechanism for dynamic depth and subgoal selection. The new algorithms remain real-time and complete. On large computer game maps, they find paths within 7% of optimal while on average expanding roughly a single state per action. This is nearly a three-fold improvement in suboptimality over the existing state-of-the-art algorithms and, at the same time, a 15-fold improvement in the amount of planning per action.
リアルタイムヒューリスティック探索は、エージェント中心の探索の中でも難しいタイプのものです。これは、エージェントの行動ごとの計画時間が、問題規模に依存しない定数によって制限されるからです。このような制約を課す一般的な問題として、現代のコンピュータゲームにおける経路探索が挙げられます。このゲームでは、多数のユニットが広大なマップ上で同時に経路を計画しなければならない。一般的な探索アルゴリズム（A*、IDA*、D*、ARA*、AD*など）は本質的にリアルタイムではなく、行動ごとの計画時間に定数の制限が課されると、完全性を失う可能性があります。リアルタイム探索アルゴリズムは完全性を維持していますが、許容できないほど準最適な解を頻繁に生成します。本稿では、動的な深度とサブゴールの選択を自動化するメカニズムを導入し、古典的および現代的なリアルタイム探索アルゴリズムを拡張します。新しいアルゴリズムはリアルタイム性と完全性を維持しています。大規模なコンピュータゲームマップにおいて、平均してアクションごとに約1つの状態を拡張しながら、最適値の7%以内のパスを見つけます。これは、既存の最先端アルゴリズムと比較して準最適性が約3倍改善され、同時にアクションごとの計画量が15倍改善されます。
On the Qualitative Comparison of Decisions Having Positive and Negative Features
正と負の特徴を持つ決定の定性比較について
Making a decision is often a matter of listing and comparing positive and negative arguments. In such cases, the evaluation scale for decisions should be considered bipolar, that is, negative and positive values should be explicitly distinguished. That is what is done, for example, in Cumulative Prospect Theory. However, contraryto the latter framework that presupposes genuine numerical assessments, human agents often decide on the basis of an ordinal ranking of the pros and the cons, and by focusing on the most salient arguments. In other terms, the decision process is qualitative as well as bipolar. In this article, based on a bipolar extension of possibility theory, we define and axiomatically characterize several decision rules tailored for the joint handling of positive and negative arguments in an ordinal setting. The simplest rules can be viewed as extensions of the maximin and maximax criteria to the bipolar case, and consequently suffer from poor decisive power. More decisive rules that refine the former are also proposed. These refinements agree both with principles of efficiency and with the spirit of order-of-magnitude reasoning, that prevails in qualitative decision theory. The most refined decision rule uses leximin rankings of the pros and the cons, and the ideas of counting arguments of equal strength and cancelling pros by cons. It is shown to come down to a special case of Cumulative Prospect Theory, and to subsume the “Take the Best” heuristic studied by cognitive psychologists.
意思決定は、多くの場合、肯定的な議論と否定的な議論を列挙し比較する作業となります。そのような場合、意思決定の評価尺度は双極性、すなわち肯定的な価値と否定的な価値を明確に区別するべきです。これは、例えば累積的プロスペクト理論において行われていることです。しかし、真の数値評価を前提とする後者の枠組みとは対照的に、人間の行為者はしばしば賛否両論の順序付けに基づき、最も顕著な議論に焦点を当てて意思決定を行う。言い換えれば、意思決定プロセスは定性的であると同時に双極性でもあります。本稿では、可能性理論の双極性拡張に基づき、順序付けされた状況において肯定的な議論と否定的な議論の両方を扱うためのいくつかの意思決定ルールを定義し、公理的に特徴付ける。最も単純なルールは、マキシミン基準とマキシマックス基準を双極性ケースに拡張したものと見なすことができ、その結果、決定力が弱い。前者を改良した、より決定力のあるルールも提案します。これらの改良は、効率性の原則と、質的意思決定理論で広く用いられている桁違い推論の精神の両方に合致します。最も改良された意思決定ルールは、賛成と反対のレキシミンランキング、そして同等の強さの議論を数え、賛成を反対で打ち消すという考え方を用いています。これは累積的プロスペクト理論の特殊なケースに帰着し、認知心理学者が研究する「最善を選ぶ」ヒューリスティックを包含することが示されます。
Extended RDF as a Semantic Foundation of Rule Markup Languages
ルールマークアップ言語の意味的基盤としての拡張RDF
Ontologies and automated reasoning are the building blocks of the Semantic Web initiative. Derivation rules can be included in an ontology to define derived concepts, based on base concepts. For example, rules allow to define the extension of a class or property, based on a complex relation between the extensions of the same or other classes and properties. On the other hand, the inclusion of negative information both in the form of negation-as-failure and explicit negative information is also needed to enable various forms of reasoning. In this paper, we extend RDF graphs with weak and strong negation, as well as derivation rules. The ERDF stable model semantics of the extended framework (Extended RDF) is defined, extending RDF(S) semantics. A distinctive feature of our theory, which is based on Partial Logic, is that both truth and falsity extensions of properties and classes are considered, allowing for truth value gaps. Our framework supports both closed-world and open-world reasoning through the explicit representation of the particular closed-world assumptions and the ERDF ontological categories of total properties and total classes.
オントロジーと自動推論は、セマンティックウェブイニシアチブの構成要素です。導出ルールをオントロジーに含めることで、基本概念に基づいて派生概念を定義できます。たとえば、規則により、同じまたは他のクラスとプロパティの拡張間の複雑な関係に基づいて、クラスまたはプロパティの拡張を定義できます。一方、失敗としての否定と明示的な否定情報の両方の形式で否定情報を含めることも、さまざまな形式の推論を可能にするために必要です。この論文では、弱い否定と強い否定、および導出規則を使用してRDFグラフを拡張します。拡張フレームワーク(拡張RDF)のERDF安定モデル意味論が定義され、RDF(S)意味論を拡張します。部分論理に基づく私たちの理論の特徴的な点は、プロパティとクラスの真と偽の両方の拡張が考慮され、真理値ギャップが許容されることです。私たちのフレームワークは、特定の閉世界仮定の明示的な表現と、全プロパティと全クラスのERDFオントロジー カテゴリを通じて、閉世界推論と開世界推論の両方をサポートします。
Spectrum of Variable-Random Trees
可変ランダムツリーのスペクトル
In this paper, we show that a continuous spectrum of randomisation exists, in which most existing tree randomisations are only operating around the two ends of the spectrum. That leaves a huge part of the spectrum largely unexplored. We propose a base learner VR-Tree which generates trees with variable-randomness. VR-Trees are able to span from the conventional deterministic trees to the complete-random trees using a probabilistic parameter. Using VR-Trees as the base models, we explore the entire spectrum of randomised ensembles, together with Bagging and Random Subspace. We discover that the two halves of the spectrum have their distinct characteristics; and the understanding of which allows us to propose a new approach in building better decision tree ensembles. We name this approach Coalescence, which coalesces a number of points in the random-half of the spectrum. Coalescence acts as a committee of “experts” to cater for unforeseeable conditions presented in training data. Coalescence is found to perform better than any single operating point in the spectrum, without the need to tune to a specific level of randomness. In our empirical study, Coalescence ranks top among the benchmarking ensemble methods including Random Forests, Random Subspace and C5 Boosting; and only Coalescence is significantly better than Bagging and Max-Diverse Ensemble among all the methods in the comparison. Although Coalescence is not significantly better than Random Forests, we have identified conditions under which one will perform better than the other.
本論文では、ランダム化には連続的なスペクトルが存在し、既存のほとんどのツリーランダム化はスペクトルの両端付近でのみ動作していることを示します。そのため、スペクトルの大部分はほとんど未調査のままです。可変ランダム性を持つツリーを生成する基本学習器VR-Treeを提案します。VR-Treeは、確率パラメータを使用して、従来の決定論的ツリーから完全ランダムツリーまでをカバーできます。VR-Treeを基本モデルとして使用し、バギングとランダムサブスペースとともに、ランダム化アンサンブルのスペクトル全体を探索します。スペクトルの2つの半分にはそれぞれ異なる特性があることを発見しました。これを理解することで、より優れた決定木アンサンブルを構築するための新たなアプローチを提案することができます。このアプローチをCoalescence（コアレセンス）と名付けました。これは、スペクトルのランダムな半分にある多数のポイントをコアレセンスするものです。Coalescenceは、トレーニングデータに現れる予測不可能な状況に対応するための「専門家」委員会のような役割を果たします。Coalescenceは、特定のランダム性レベルに調整する必要なく、スペクトル内のどの単一の動作ポイントよりも優れたパフォーマンスを発揮することが分かっています。私たちの実証的研究では、Coalescenceは、ランダムフォレスト、ランダムサブスペース、C5ブースティングなどのベンチマークアンサンブル手法の中でトップにランクされています。また、比較対象となったすべての手法の中で、CoalescenceのみがバギングとMax-Diverseアンサンブルよりも大幅に優れています。Coalescenceはランダムフォレストよりも大幅に優れているわけではありませんが、どちらかが他方よりも優れたパフォーマンスを発揮する条件を特定しました。
Optimal and Approximate Q-value Functions for Decentralized POMDPs
分散POMDPのための最適および近似Q値関数
Decision-theoretic planning is a popular approach to sequential decision making problems, because it treats uncertainty in sensing and acting in a principled way. In single-agent frameworks like MDPs and POMDPs, planning can be carried out by resorting to Q-value functions: an optimal Q-value function Q* is computed in a recursive manner by dynamic programming, and then an optimal policy is extracted from Q*. In this paper we study whether similar Q-value functions can be defined for decentralized POMDP models (Dec-POMDPs), and how policies can be extracted from such value functions. We define two forms of the optimal Q-value function for Dec-POMDPs: one that gives a normative description as the Q-value function of an optimal pure joint policy and another one that is sequentially rational and thus gives a recipe for computation. This computation, however, is infeasible for all but the smallest problems. Therefore, we analyze various approximate Q-value functions that allow for efficient computation. We describe how they relate, and we prove that they all provide an upper bound to the optimal Q-value function Q*. Finally, unifying some previous approaches for solving Dec-POMDPs, we describe a family of algorithms for extracting policies from such Q-value functions, and perform an experimental evaluation on existing test problems, including a new firefighting benchmark problem.
決定理論的計画は、感知と行動における不確実性を原理的に扱うため、逐次的な意思決定問題に対する一般的なアプローチです。MDPやPOMDPのようなシングルエージェントフレームワークでは、Q値関数を用いて計画を実行できます。最適なQ値関数Q*は動的計画法によって再帰的に計算され、Q*から最適な方策が抽出されます。本稿では、同様のQ値関数が分散型POMDPモデル（Dec-POMDP）に対して定義可能かどうか、またそのような値関数から方策をどのように抽出できるかを検討します。Dec-POMDPの最適Q値関数を2種類定義します。1つは最適な純粋結合方策のQ値関数として規範的な記述を与えるもので、もう1つは逐次的に合理的なため計算のレシピを与えるものです。しかし、この計算はごく小さな問題を除いて実行不可能です。そこで、効率的な計算を可能にする様々な近似Q値関数を分析します。これらがどのように関連しているかを説明し、それらがすべて最適なQ値関数Q*の上限を提供することを証明します。最後に、Dec-POMDPを解くためのいくつかの以前のアプローチを統合し、そのようなQ値関数からポリシーを抽出するためのアルゴリズムのファミリーを説明し、新しい消防ベンチマーク問題を含む既存のテスト問題に対する実験的評価を実行します。
New Islands of Tractability of Cost-Optimal Planning
コスト最適計画の新たな扱いやすさの島々
We study the complexity of cost-optimal classical planning over propositional state variables and unary-effect actions. We discover novel problem fragments for which such optimization is tractable, and identify certain conditions that differentiate between tractable and intractable problems. These results are based on exploiting both structural and syntactic characteristics of planning problems. Specifically, following Brafman and Domshlak (2003), we relate the complexity of planning and the topology of the causal graph. The main results correspond to tractability of cost-optimal planning for propositional problems with polytree causal graphs that either have O(1)-bounded in-degree, or are induced by actions having at most one prevail condition each. Almost all our tractability results are based on a constructive proof technique that connects between certain tools from planning and tractable constraint optimization, and we believe this technique is of interest on its own due to a clear evidence for its robustness.
命題状態変数と単項効果アクションに対するコスト最適古典的プランニングの複雑さを調査します。このような最適化が扱いやすい新しい問題フラグメントを発見し、扱いやすい問題と扱いにくい問題を区別する特定の条件を特定します。これらの結果は、プランニング問題の構造的特性と構文的特性の両方を活用することに基づいています。具体的には、Brafman and Domshlak (2003)に従い、プランニングの複雑さと因果グラフの位相を関連付ける。主な結果は、入次数がO(1)に制限されているか、またはそれぞれ最大で1つの優先条件を持つアクションによって誘導される、多木因果グラフを持つ命題問題に対するコスト最適プランニングの扱いやすさに対応します。私たちの扱いやすさに関する結果のほぼすべては、計画と扱いやすい制約の最適化の特定のツール間を接続する構成的証明手法に基づいており、この手法は堅牢性に関する明確な証拠があるため、それ自体が興味深いものであると考えています。
Communication-Based Decomposition Mechanisms for Decentralized MDPs
分散MDPのための通信ベースの分解メカニズム
Multi-agent planning in stochastic environments can be framed formally as a decentralized Markov decision problem. Many real-life distributed problems that arise in manufacturing, multi-robot coordination and information gathering scenarios can be formalized using this framework. However, finding the optimal solution in the general case is hard, limiting the applicability of recently developed algorithms. This paper provides a practical approach for solving decentralized control problems when communication among the decision makers is possible, but costly. We develop the notion of communication-based mechanism that allows us to decompose a decentralized MDP into multiple single-agent problems. In this framework, referred to as decentralized semi-Markov decision process with direct communication (Dec-SMDP-Com), agents operate separately between communications. We show that finding an optimal mechanism is equivalent to solving optimally a Dec-SMDP-Com. We also provide a heuristic search algorithm that converges on the optimal decomposition. Restricting the decomposition to some specific types of local behaviors reduces significantly the complexity of planning. In particular, we present a polynomial-time algorithm for the case in which individual agents perform goal-oriented behaviors between communications. The paper concludes with an additional tractable algorithm that enables the introduction of human knowledge, thereby reducing the overall problem to finding the best time to communicate. Empirical results show that these approaches provide good approximate solutions.
確率的環境におけるマルチエージェントプランニングは、分散型マルコフ決定問題として形式的に定式化できます。製造業、複数ロボットの協調、情報収集といった現実の分散問題の多くは、この枠組みを用いて形式化できます。しかし、一般的なケースでは最適解を求めることが困難であり、最近開発されたアルゴリズムの適用範囲が限られています。本稿では、意思決定者間の通信は可能だがコストがかかる分散制御問題を解くための実用的なアプローチを提示します。我々は、分散型MDPを複数のシングルエージェント問題に分解することを可能にする通信ベースメカニズムの概念を開発します。直接通信を伴う分散型セミマルコフ決定プロセス（Dec-SMDP-Com）と呼ばれるこの枠組みでは、エージェントは通信ごとに個別に動作します。最適なメカニズムを見つけることは、Dec-SMDP-Comを最適に解くことと等価であることを示す。また、最適な分解に収束するヒューリスティックな探索アルゴリズムも提供します。分解を特定の種類の局所行動に限定することで、プランニングの複雑さを大幅に軽減します。特に、個々のエージェントが通信の合間に目標指向行動を実行する場合の多項式時間アルゴリズムを提示します。本論文は、人間の知識を導入することを可能にする追加の扱いやすいアルゴリズムで結論付けており、これにより全体的な問題は通信に最適なタイミングを見つけることに簡略化されます。実験結果は、これらのアプローチが良好な近似解を提供することを示す。
A Constraint Programming Approach for Solving a Queueing Control Problem
待ち行列制御問題を解くための制約計画法によるアプローチ
In a facility with front room and back room operations, it is useful to switch workers between the rooms in order to cope with changing customer demand. Assuming stochastic customer arrival and service times, we seek a policy for switching workers such that the expected customer waiting time is minimized while the expected back room staffing is sufficient to perform all work. Three novel constraint programming models and several shaving procedures for these models are presented. Experimental results show that a model based on closed-form expressions together with a combination of shaving procedures is the most efficient. This model is able to find and prove optimal solutions for many problem instances within a reasonable run-time. Previously, the only available approach was a heuristic algorithm. Furthermore, a hybrid method combining the heuristic and the best constraint programming method is shown to perform as well as the heuristic in terms of solution quality over time, while achieving the same performance in terms of proving optimality as the pure constraint programming model. This is the first work of which we are aware that solves such queueing-based problems with constraint programming.
フロントルームとバックルームを備えた施設では、変化する顧客需要に対応するために、フロントルームとバックルーム間で作業員を交代することが有用です。顧客到着とサービス時間は確率的であると仮定し、バックルームの人員配置がすべての作業を遂行するのに十分な人数である一方で、顧客の予想待ち時間が最小となるような作業員交代ポリシーを模索します。3つの新しい制約プログラミングモデルと、これらのモデルのための複数のシェービング手順を提示します。実験結果から、閉形式表現とシェービング手順の組み合わせに基づくモデルが最も効率的であることが示されました。このモデルは、多くの問題インスタンスに対して、妥当な実行時間内で最適解を見つけ出し、証明することができます。これまで利用可能な唯一のアプローチは、ヒューリスティックアルゴリズムであった。さらに、ヒューリスティックと最適な制約プログラミング手法を組み合わせたハイブリッド手法は、時間経過に伴う解の品質においてヒューリスティックと同等の性能を示し、最適性の証明においては純粋な制約プログラミングモデルと同等の性能を達成することが示されました。これは、制約プログラミングを用いてこのような待ち行列ベースの問題を解く、我々が知る限り最初の研究です。
Cooperative Search with Concurrent Interactions
同時インタラクションを伴う協調探索
In this paper we show how taking advantage of autonomous agents’ capability to maintain parallel interactions with others, and incorporating it into the cooperative economic search model results in a new search strategy which outperforms current strategies in use. As a framework for our analysis we use the electronic marketplace, where buyer agents have the incentive to search cooperatively. The new search technique is quite intuitive, however its analysis and the process of extracting the optimal search strategy are associated with several significant complexities. These difficulties are derived mainly from the unbounded search space and simultaneous dual affects of decisions taken along the search. We provide a comprehensive analysis of the model, highlighting, demonstrating and proving important characteristics of the optimal search strategy. Consequently, we manage to come up with an efficient modular algorithm for extracting the optimal cooperative search strategy for any given environment. A computational based comparative illustration of the system performance using the new search technique versus the traditional methods is given, emphasizing the main differences in the optimal strategy’s structure and the advantage of using the proposed model.
本稿では、自律エージェントが他者と並行して相互作用を維持する能力を活用し、それを協力的経済探索モデルに組み込むことで、現在使用されている戦略よりも優れた新しい探索戦略がどのように実現されるかを示す。分析の枠組みとして、購買エージェントが協力的に探索するインセンティブを持つ電子市場を用います。この新しい探索手法は非常に直感的であるが、その分析と最適な探索戦略の抽出プロセスには、いくつかの大きな複雑さが伴う。これらの困難は主に、無限の探索空間と、探索中に下される意思決定の同時的な二重効果に起因しています。本稿では、モデルの包括的な分析を行い、最適探索戦略の重要な特性を明らかにし、実証し、証明します。その結果、任意の環境に最適な協力探索戦略を抽出するための効率的なモジュール型アルゴリズムを考案した。また、新しい探索手法と従来の手法を用いたシステム性能を計算に基づいて比較し、最適戦略の構造における主な違いと、提案モデルを使用する利点を強調します。