Solving Limited Memory Influence Diagrams
限られたメモリの影響図の解法
We present a new algorithm for exactly solving decision making problems represented as influence diagrams. We do not require the usual assumptions of no forgetting and regularity; this allows us to solve problems with simultaneous decisions and limited information. The algorithm is empirically shown to outperform a state-of-the-art algorithm on randomly generated problems of up to 150 variables and 10^64 solutions. We show that these problems are NP-hard even if the underlying graph structure of the problem has low treewidth and the variables take on a bounded number of states, and that they admit no provably good approximation if variables can take on an arbitrary number of states.
本研究では、影響図として表現される意思決定問題を正確に解くための新しいアルゴリズムを提示します。忘却や正則性といった通常の仮定は不要です。これにより、同時決定や限られた情報を伴う問題を解くことができます。このアルゴリズムは、最大150変数、10の64乗の解を持つランダム生成問題において、最先端のアルゴリズムよりも優れた性能を示すことが経験的に示されています。問題の根底にあるグラフ構造の木幅が狭く、変数が有限個の状態をとる場合でも、これらの問題はNP困難であり、変数が任意の個数の状態をとる場合には、証明可能な良好な近似は存在しないことを示す。
Online Speedup Learning for Optimal Planning
最適計画のためのオンライン高速化学習
Domain-independent planning is one of the foundational areas in the field of Artificial Intelligence. A description of a planning task consists of an initial world state, a goal, and a set of actions for modifying the world state. The objective is to find a sequence of actions, that is, a plan, that transforms the initial world state into a goal state. In optimal planning, we are interested in finding not just a plan, but one of the cheapest plans. A prominent approach to optimal planning these days is heuristicstate-space search, guided by admissible heuristic functions. Numerous admissible heuristics have been developed, each with its own strengths and weaknesses, and it is well known that there is no single “best” heuristic for optimal planning in general. Thus, which heuristic to choose for a given planning task is a difficult question. This difficulty can be avoided by combining several heuristics, but that requires computing numerous heuristic estimates at each state, and the tradeoff between the time spent doing so and the time saved by the combined advantages of the different heuristics might be high. We present a novel method that reduces the cost of combining admissible heuristics for optimal planning, while maintaining its benefits. Using an idealized search space model, we formulate a decision rule for choosing the best heuristic to compute at each state. We then present an active online learning approach for learning a classifier with that decision rule as the target concept, and employ the learned classifier to decide which heuristic to compute at each state. We evaluate this technique empirically, and show that it substantially outperforms the standard method for combining several heuristics via their pointwise maximum.
ドメイン非依存プランニングは、人工知能分野における基礎的な分野の一つです。プランニングタスクの記述は、初期世界状態、目標、そして世界状態を変更するための一連のアクションで構成されます。目標は、初期世界状態を目標状態に変換する一連のアクション、つまりプランを見つけることです。最適プランニングでは、単なるプランではなく、最もコストの低いプランを見つけることに重点が置かれます。近年、最適プランニングへの有力なアプローチは、許容ヒューリスティック関数に基づくヒューリスティックな状態空間探索です。数多くの許容ヒューリスティックが開発されており、それぞれに長所と短所があり、一般的に最適な計画のための単一の「最良の」ヒューリスティックは存在しないことはよく知られています。したがって、特定の計画タスクにどのヒューリスティックを選択すべきかは難しい問題です。この困難は複数のヒューリスティックを組み合わせることで回避できますが、各状態において多数のヒューリスティック推定値を計算する必要があり、計算にかかる時間と、異なるヒューリスティックの利点を組み合わせることで節約される時間との間のトレードオフは大きくなる可能性があります。本稿では、最適計画のための許容ヒューリスティックの組み合わせにかかるコストを削減しつつ、その利点を維持する新しい手法を提示します。理想化された探索空間モデルを用いて、各状態において計算する最適なヒューリスティックを選択するための決定規則を定式化します。次に、その決定規則を目標概念として分類器を学習するための能動的なオンライン学習手法を提示し、学習した分類器を用いて各状態においてどのヒューリスティックを計算するかを決定します。本手法を経験的に評価し、複数のヒューリスティックを組み合わせる標準的な手法よりも大幅に優れていることを示します。点ごとの最大値。
The Logical Difference for the Lightweight Description Logic EL
軽量記述論理ELの論理的差異
We study a logic-based approach to versioning of ontologies. Under this view, ontologies provide answers to queries about some vocabulary of interest. The difference between two versions of an ontology is given by the set of queries that receive different answers.We investigate this approach for terminologies given in the description logic EL extended with role inclusions and domain and range restrictions for three distinct types of queries: subsumption, instance, and conjunctive queries. In all three cases, we present polynomial-time algorithms that decide whether two terminologies give the same answers to queries over a given vocabulary and compute a succinct representation of the difference if it is non-empty. We present an implementation, CEX2, of the developed algorithms for subsumption and instance queries and apply it to distinct versions of Snomed CT and the NCI ontology.
本研究では、オントロジーのバージョン管理に対する論理ベースのアプローチを研究します。この観点から、オントロジーは、関心のある語彙に関するクエリへの回答を提供します。オントロジーの2つのバージョンの違いは、異なる回答を受け取るクエリの集合によって示されます。本研究では、役割の包含と定義域および値域の制限を拡張した記述論理ELで提供される用語集を対象に、包摂、インスタンス、および結合クエリという3つの異なる種類のクエリに対してこのアプローチを調査します。3つのケースすべてにおいて、2つの用語集が特定の語彙に関するクエリに対して同じ回答を返すかどうかを判定し、空でない場合はその差異の簡潔な表現を計算する多項式時間アルゴリズムを提示します。包摂およびインスタンスクエリ用に開発されたアルゴリズムの実装であるCEX2を提示し、それをSnomed CTとNCIオントロジーの異なるバージョンに適用します。
SAP Speaks PDDL: Exploiting a Software-Engineering Model for Planning in Business Process Management
SAP Speaks PDDL：ビジネスプロセス管理における計画のためのソフトウェアエンジニアリングモデルの活用
Planning is concerned with the automated solution of action sequencing problems described in declarative languages giving the action preconditions and effects. One important application area for such technology is the creation of new processes in Business Process Management (BPM), which is essential in an ever more dynamic business environment. A major obstacle for the application of Planning in this area lies in the modeling. Obtaining a suitable model to plan with — ideally a description in PDDL, the most commonly used planning language — is often prohibitively complicated and/or costly. Our core observation in this work is that this problem can be ameliorated by leveraging synergies with model-based software development. Our application at SAP, one of the leading vendors of enterprise software, demonstrates that even one-to-one model re-use is possible.The model in question is called Status and Action Management (SAM). It describes the behavior of Business Objects (BO), i.e., large-scale data structures, at a level of abstraction corresponding to the language of business experts. SAM covers more than 400 kinds of BOs, each of which is described in terms of a set of status variables and how their values are required for, and affected by, processing steps (actions) that are atomic from a business perspective. SAM was developed by SAP as part of a major model-based software engineering effort. We show herein that one can use this same model for planning, thus obtaining a BPM planning application that incurs no modeling overhead at all.We compile SAM into a variant of PDDL, and adapt an off-the-shelf planner to solve this kind of problem. Thanks to the resulting technology, business experts may create new processes simply by specifying the desired behavior in terms of status variable value changes: effectively, by describing the process in their own language.
プランニングは、アクションの前提条件と効果を与える宣言型言語で記述されたアクションシーケンスの問題を自動的に解決することに関係しています。このような技術の重要な応用分野の一つは、ビジネスプロセス管理（BPM）における新しいプロセスの作成であり、これはますますダイナミックになるビジネス環境において不可欠です。この分野におけるプランニングの適用における大きな障害は、モデリングにあります。プランニングに適したモデル（理想的には最も一般的に使用されているプランニング言語であるPDDLによる記述）を入手することは、しばしば非常に複雑で、コストがかかります。本研究における私たちの中心的な考察は、この問題はモデルベースソフトウェア開発との相乗効果を活用することで改善できるという点です。エンタープライズソフトウェアの主要ベンダーであるSAPにおける私たちのアプリケーションは、1対1のモデル再利用さえも可能であることを実証しています。問題のモデルは、ステータスおよびアクション管理（SAM）と呼ばれます。これは、ビジネスオブジェクト（BO）、すなわち大規模データ構造の挙動を、ビジネス専門家の言語に対応する抽象レベルで記述します。SAMは400種類以上のBOをカバーしており、それぞれのBOは、一連のステータス変数と、それらの値がビジネスの観点からアトミックな処理ステップ（アクション）にどのように必要とされ、どのように影響を受けるかという観点から記述されます。SAMは、モデルベースソフトウェアエンジニアリングの主要な取り組みの一環としてSAPによって開発されました。本稿では、この同じモデルを計画にも使用できることを示すことで、モデリングのオーバーヘッドを全く発生させないBPM計画アプリケーションを実現します。SAMをPDDLのバリアントにコンパイルし、市販のプランナーを適応させることで、この種の問題を解決します。得られた技術のおかげで、ビジネスエキスパートは、ステータス変数の値の変化という観点から望ましい動作を指定するだけで、新しいプロセスを作成できます。つまり、プロセスを自分の言語で記述することで、実質的に新しいプロセスを作成できます。
Domain and Function: A Dual-Space Model of Semantic Relations and Compositions
ドメインと機能：意味的関係と構成の双対空間モデル
Given appropriate representations of the semantic relations between carpenter and wood and between mason and stone (for example, vectors in a vector space model), a suitable algorithm should be able to recognize that these relations are highly similar (carpenter is to wood as mason is to stone; the relations are analogous). Likewise, with representations of dog, house, and kennel, an algorithm should be able to recognize that the semantic composition of dog and house, dog house, is highly similar to kennel (dog house and kennel are synonymous). It seems that these two tasks, recognizing relations and compositions, are closely connected. However, up to now, the best models for relations are significantly different from the best models for compositions. In this paper, we introduce a dual-space model that unifies these two tasks. This model matches the performance of the best previous models for relations and compositions. The dual-space model consists of a space for measuring domain similarity and a space for measuring function similarity. Carpenter and wood share the same domain, the domain of carpentry. Mason and stone share the same domain, the domain of masonry. Carpenter and mason share the same function, the function of artisans. Wood and stone share the same function, the function of materials. In the composition dog house, kennel has some domain overlap with both dog and house (the domains of pets and buildings). The function of kennel is similar to the function of house (the function of shelters). By combining domain and function similarities in various ways, we can model relations, compositions, and other aspects of semantics.
大工と木材、そして石工と石材の関係を適切に表現（例えば、ベクトル空間モデルのベクトル）すれば、適切なアルゴリズムはこれらの関係が非常に類似していることを認識できるはずです（大工と木材の関係は石工と石材の関係と同じで、関係は相似です）。同様に、犬、家、犬小屋の表現を用いると、犬と家、犬小屋の意味的構成が犬小屋と非常に類似していることを認識できるはずです（犬小屋と犬小屋は同義です）。関係と構成を認識するというこの2つのタスクは密接に関連しているように見えます。しかしながら、これまでのところ、関係の最適なモデルは構成の最適なモデルとは大きく異なっています。本稿では、これら2つのタスクを統合するデュアルスペースモデルを紹介します。このモデルは、関係と構成に関するこれまでの最良のモデルと同等の性能を発揮します。デュアルスペースモデルは、ドメインの類似性を測定する空間と機能の類似性を測定する空間で構成されています。大工と木材は、大工という同じドメインを共有しています。石工と石材は同じドメイン、すなわち石工のドメインを共有しています。大工と石工は同じ機能、すなわち職人の機能を共有しています。木材と石材は同じ機能、すなわち材料の機能を共有しています。犬小屋という構成において、犬小屋は犬と家（ペットと建物のドメイン）の両方とドメインが一部重複しています。犬小屋の機能は家（シェルターの機能）の機能に類似しています。ドメインと機能の類似性を様々な方法で組み合わせることで、関係、構成、その他のセマンティクスの側面をモデル化することができます。
Riffled Independence for Efficient Inference with Partial Rankings
部分ランキングを用いた効率的な推論のためのリフィルド独立性
Distributions over rankings are used to model data in a multitude of real world settings such as preference analysis and political elections. Modeling such distributions presents several computational challenges, however, due to the factorial size of the set of rankings over an item set. Some of these challenges are quite familiar to the artificial intelligence community, such as how to compactly represent a distribution over a combinatorially large space, and how to efficiently perform probabilistic inference with these representations. With respect to ranking, however, there is the additional challenge of what we refer to as human task complexity users are rarely willing to provide a full ranking over a long list of candidates, instead often preferring to provide partial ranking information.Simultaneously addressing all of these challenges i.e., designing a compactly representable model which is amenable to efficient inference and can be learned using partial ranking data is a difficult task, but is necessary if we would like to scale to problems with nontrivial size. In this paper, we show that the recently proposed riffled independence assumptions cleanly and efficiently address each of the above challenges. In particular, we establish a tight mathematical connection between the concepts of riffled independence and of partial rankings. This correspondence not only allows us to then develop efficient and exact algorithms for performing inference tasks using riffled independence based represen- tations with partial rankings, but somewhat surprisingly, also shows that efficient inference is not possible for riffle independent models (in a certain sense) with observations which do not take the form of partial rankings. Finally, using our inference algorithm, we introduce the first method for learning riffled independence based models from partially ranked data.
ランキング上の分布は、選好分析や選挙など、さまざまな現実世界の設定でデータをモデル化するために使用されます。ただし、このような分布のモデル化には、アイテムセット上のランキング集合の階乗サイズのために、いくつかの計算上の課題があります。これらの課題のいくつかは、人工知能コミュニティでは非常によく知られており、たとえば、組み合わせ的に大きな空間上の分布をコンパクトに表現する方法や、これらの表現を使用して確率的推論を効率的に実行する方法などがあります。しかし、ランキングに関しては、いわゆる「人間のタスク複雑性」という追加の課題があります。ユーザーは、候補リスト全体にわたる完全なランキングを提供することをほとんど望まず、代わりに部分的なランキング情報を提供することを好むことが多いのです。これらの課題すべてに同時に対処すること、すなわち、効率的な推論が可能で、部分的なランキングデータを用いて学習可能な、コンパクトに表現可能なモデルを設計することは困難な作業ですが、大規模な問題に拡張するためには不可欠です。本論文では、最近提案されたリフル独立性仮定が、上記の各課題を明確かつ効率的に解決することを示します。特に、リフル独立性と部分ランキングの概念の間に密接な数学的関連性を確立します。この対応関係により、部分ランキングを含むリフル独立性に基づく表現を用いて推論タスクを実行するための効率的かつ正確なアルゴリズムを開発できるだけでなく、驚くべきことに、部分ランキングの形をとらない観測値を持つリフル独立性モデル（ある意味で）では、効率的な推論が不可能であることも示されます。最後に、私たちの推論アルゴリズムを使用して、部分的にランク付けされたデータからリフル独立性に基づくモデルを学習する最初の方法を紹介します。
Tractable Triangles and Cross-Free Convexity in Discrete Optimisation
離散最適化における扱いやすい三角形と交差フリー凸性
The minimisation problem of a sum of unary and pairwise functions of discrete variables is a general NP-hard problem with wide applications such as computing MAP configurations in Markov Random Fields (MRF), minimising Gibbs energy, or solving binary Valued Constraint Satisfaction Problems (VCSPs).We study the computational complexity of classes of discrete optimisation problems given by allowing only certain types of costs in every triangle of variable-value assignments to three distinct variables. We show that for several computational problems, the only non- trivial tractable classes are the well known maximum matching problem and the recently discovered joint-winner property. Our results, apart from giving complete classifications in the studied cases, provide guidance in the search for hybrid tractable classes; that is, classes of problems that are not captured by restrictions on the functions (such as submodularity) or the structure of the problem graph (such as bounded treewidth).Furthermore, we introduce a class of problems with convex cardinality functions on cross-free sets of assignments. We prove that while imposing only one of the two conditions renders the problem NP-hard, the conjunction of the two gives rise to a novel tractable class satisfying the cross-free convexity property, which generalises the joint-winner property to problems of unbounded arity.
離散変数の単項関数および対関数の和の最小化問題は、マルコフ確率場（MRF）におけるMAP構成の計算、ギブスエネルギーの最小化、2値制約充足問題（VCSP）の解法など、幅広い応用を持つ一般的なNP困難問題です。我々は、3つの異なる変数への変数値割り当ての三角形ごとに特定の種類のコストのみを許容する離散最適化問題のクラスの計算複雑性について検討します。いくつかの計算問題において、非自明で扱いやすいクラスは、よく知られている最大マッチング問題と最近発見された共同勝者特性のみであることを示す。我々の結果は、研究対象ケースにおける完全な分類を与えるだけでなく、ハイブリッドな扱いやすいクラスの探索における指針を提供します。つまり、関数の制約(劣モジュラ性など)や問題グラフの構造(木幅の制限など)によって捉えられない問題のクラスです。さらに、交差フリー割り当て集合上の凸カーディナリティ関数を伴う問題のクラスを導入します。2つの条件のうち1つだけを課すと問題がNP困難になりますが、2つの条件を組み合わせると交差フリー凸性プロパティを満たす新しい扱いやすいクラスが生成され、これにより共同勝者プロパティが無制限アリティの問題に一般化されます。
Modelling Observation Correlations for Active Exploration and Robust Object Detection
能動的な探索とロバストな物体検出のための観測相関のモデリング
Today, mobile robots are expected to carry out increasingly complex tasks in multifarious, real-world environments. Often, the tasks require a certain semantic understanding of the workspace. Consider, for example, spoken instructions from a human collaborator referring to objects of interest; the robot must be able to accurately detect these objects to correctly understand the instructions. However, existing object detection, while competent, is not perfect. In particular, the performance of detection algorithms is commonly sensitive to the position of the sensor relative to the objects in the scene.This paper presents an online planning algorithm which learns an explicit model of the spatial dependence of object detection and generates plans which maximize the expected performance of the detection, and by extension the overall plan performance. Crucially, the learned sensor model incorporates spatial correlations between measurements, capturing the fact that successive measurements taken at the same or nearby locations are not independent. We show how this sensor model can be incorporated into an efficient forward search algorithm in the information space of detected objects, allowing the robot to generate motion plans efficiently. We investigate the performance of our approach by addressing the tasks of door and text detection in indoor environments and demonstrate significant improvement in detection performance during task execution over alternative methods in simulated and real robot experiments.
今日、移動ロボットは、多様で多様な現実世界環境において、ますます複雑なタスクを実行することが期待されています。多くの場合、これらのタスクは作業空間に関する一定の意味的理解を必要とします。例えば、人間の協力者から関心のある物体に関する音声指示を考えてみましょう。ロボットが指示を正しく理解するためには、これらの物体を正確に検出できなければなりません。しかし、既存の物体検出は優れた性能を持つものの、完璧ではありません。特に、検出アルゴリズムの性能は、シーン内の物体に対するセンサーの相対的な位置に大きく左右されるのが一般的です。本論文では、物体検出の空間依存性に関する明示的なモデルを学習し、検出の期待性能、ひいては計画全体の性能を最大化する計画を生成するオンライン計画アルゴリズムを提示します。重要なのは、学習されたセンサーモデルが測定値間の空間的相関を組み込んでおり、同一または近傍の場所で連続的に測定された測定値が独立ではないという事実を捉えていることです。本論文では、このセンサーモデルを、検出物体の情報空間における効率的な順方向探索アルゴリズムに組み込むことで、ロボットが効率的に動作計画を生成できるようにする方法を示します。我々は、屋内環境におけるドアとテキストの検出というタスクを対象とする本手法の性能を調査し、シミュレーションおよび実ロボット実験において、タスク実行中の他の手法と比較して検出性能が大幅に向上することを実証した。
Semantic Similarity Measures Applied to an Ontology for Human-Like Interaction
人間のようなインタラクションのためのオントロジーに適用された意味的類似度尺度
The focus of this paper is the calculation of similarity between two concepts from an ontology for a Human-Like Interaction system. In order to facilitate this calculation, a similarity function is proposed based on five dimensions (sort, compositional, essential, restrictive and descriptive) constituting the structure of ontological knowledge. The paper includes a proposal for computing a similarity function for each dimension of knowledge. Later on, the similarity values obtained are weighted and aggregated to obtain a global similarity measure. In order to calculate those weights associated to each dimension, four training methods have been proposed. The training methods differ in the element to fit: the user, concepts or pairs of concepts, and a hybrid approach. For evaluating the proposal, the knowledge base was fed from WordNet and extended by using a knowledge editing toolkit (Cognos). The evaluation of the proposal is carried out through the comparison of system responses with those given by human test subjects, both providing a measure of the soundness of the procedure and revealing ways in which the proposal may be improved.
本論文では、人間のようなインタラクションシステムのオントロジーにおける2つの概念間の類似度の計算に焦点を当てます。この計算を容易にするために、オントロジー知識の構造を構成する5つの次元(ソート、構成、必須、制限、および記述)に基づく類似度関数が提案されています。この論文では、知識の各次元について類似度関数を計算するための提案が含まれています。その後、得られた類似度値は重み付けされ、集計されて、全体的な類似度尺度が得られます。各次元に関連付けられた重みを計算するために、4つのトレーニング方法が提案されています。これらのトレーニング方法は、適合する要素が異なり、ユーザー、概念または概念のペア、およびハイブリッド アプローチがあります。提案を評価するために、知識ベースはWordNetから入力され、知識編集ツールキット(Cognos)を使用して拡張されました。提案の評価は、システム応答と人間の被験者による応答を比較することによって行われ、手順の健全性の尺度と、提案を改善できる方法の両方が提供されます。
Narrative Planning: Compilations to Classical Planning
ナラティブプランニング：古典的プランニングへのコンパイル
A model of story generation recently proposed by Riedl and Youngcasts it as planning, with the additional condition that storycharacters behave intentionally. This means that characters haveperceivable motivation for the actions they take. I show that thiscondition can be compiled away (in more ways than one) to produce aclassical planning problem that can be solved by an off-the-shelfclassical planner, more efficiently than by Riedl and Young’sspecialised planner.
RiedlとYoungによって最近提案されたストーリー生成モデルは、ストーリーの登場人物が意図的に行動するという条件を追加したプランニングとして捉えています。これは、登場人物が自分の行動に対して知覚可能な動機を持っていることを意味します。私は、この条件を（複数の方法で）コンパイルすることで、RiedlとYoungの専用プランナーよりも効率的に、既製の古典的なプランナーで解決できる古典的なプランニング問題を生成することができることを示します。
Plan-based Policies for Efficient Multiple Battery Load Management
効率的な複数バッテリー負荷管理のための計画ベースポリシー
Efficient use of multiple batteries is a practical problem with wide and growing application. The problem can be cast as a planning problem under uncertainty. We describe the approach we have adopted to modelling and solving this problem, seen as a Markov Decision Problem, building effective policies for battery switching in the face of stochastic load profiles. Our solution exploits and adapts several existing techniques: planning for deterministic mixed discrete-continuous problems and Monte Carlo sampling for policy learning. The paper describes the development of planning techniques to allow solution of the non-linear continuous dynamic models capturing the battery behaviours. This approach depends on carefully handled discretisation of the temporal dimension. The construction of policies is performed using a classification approach and this idea offers opportunities for wider exploitation in other problems. The approach and its generality are described in the paper.Application of the approach leads to construction of policies that, in simulation, significantly outperform those that are currently in use and the best published solutions to the battery management problem. We achieve solutions that achieve more than 99% efficiency in simulation compared with the theoretical limit and do so with far fewer battery switches than existing policies. Behaviour of physical batteries does not exactly match the simulated models for many reasons, so to confirm that our theoretical results can lead to real measured improvements in performance we also conduct and report experiments using a physical test system. These results demonstrate that we can obtain 5%-15% improvement in lifetimes in the case of a two battery system.
複数のバッテリーを効率的に使用することは、幅広く応用が拡大している実用的な問題です。この問題は、不確実性を考慮した計画問題として捉えることができます。本稿では、この問題をマルコフ決定問題としてモデル化し、確率的な負荷プロファイルを考慮したバッテリー切り替えのための効果的なポリシーを構築するアプローチについて説明します。このソリューションは、決定論的な離散・連続混合問題のための計画手法と、ポリシー学習のためのモンテカルロサンプリング手法といった既存の手法を活用・適応させています。本稿では、バッテリーの挙動を捉える非線形連続動的モデルの解法を可能にする計画手法の開発について説明します。このアプローチは、時間軸の離散化を慎重に処理することに依存しています。ポリシーの構築は分類アプローチを用いて行われ、このアイデアは他の問題にも広く活用できる可能性があります。本稿では、このアプローチとその汎用性について説明します。このアプローチを適用することで、シミュレーションにおいて、現在使用されているポリシーやバッテリー管理問題に対する最良の公開ソリューションを大幅に上回るポリシーを構築できます。理論限界と比較してシミュレーションで99%以上の効率を達成するソリューションを、既存のポリシーよりもはるかに少ないバッテリー交換で実現しました。物理的なバッテリーの挙動は、多くの理由からシミュレーションモデルと完全には一致しません。そのため、理論上の結果が実際に測定された性能向上につながることを確認するために、物理的なテストシステムを用いた実験も実施し、報告します。これらの結果は、2つのバッテリーシステムの場合、寿命が5%～15%向上することを示しています。
Algorithms for Generating Ordered Solutions for Explicit AND/OR Structures
明示的なAND/OR構造に対する順序付き解を生成するアルゴリズム
We present algorithms for generating alternative solutions for explicit acyclic AND/OR structures in non-decreasing order of cost. The proposed algorithms use a best first search technique and report the solutions using an implicit representation ordered by cost. In this paper, we present two versions of the search algorithm — (a) an initial version of the best first search algorithm, ASG, which may present one solution more than once while generating the ordered solutions, and (b) another version, LASG, which avoids the construction of the duplicate solutions. The actual solutions can be reconstructed quickly from the implicit compact representation used. We have applied the methods on a few test domains, some of them are synthetic while the others are based on well known problems including the search space of the 5-peg Tower of Hanoi problem, the matrix-chain multiplication problem and the problem of finding secondary structure of RNA. Experimental results show the efficacy of the proposed algorithms over the existing approach. Our proposed algorithms have potential use in various domains ranging from knowledge based frameworks to service composition, where the AND/OR structure is widely used for representing problems.
明示的な非巡回AND/OR構造に対し、コストの非減少順に代替解を生成するアルゴリズムを提案します。提案するアルゴリズムは、最良優先探索法を用い、コスト順に順序付けられた暗黙的表現を用いて解を報告します。本稿では、この探索アルゴリズムの2つのバージョンを提示します。(a)最良優先探索アルゴリズムの初期バージョンであるASGは、順序付けられた解を生成する際に1つの解を複数回提示する可能性があります。(b)重複解の構築を回避する別のバージョンであるLASGは、使用される暗黙的コンパクト表現から迅速に再構成できます。これらの手法をいくつかのテストドメインに適用した。これらのドメインの一部は合成問題であり、その他は5ペグハノイの塔問題の探索空間、行列連鎖乗算問題、RNAの二次構造探索問題など、よく知られた問題に基づいています。実験結果は、提案アルゴリズムが既存のアプローチよりも有効であることを示しています。提案アルゴリズムは、知識ベースフレームワークからサービス合成まで、AND/OR構造が問題の表現に広く用いられている様々な分野で活用できる可能性があります。
Modeling Social Causality and Responsibility Judgment in Multi-Agent Interactions
マルチエージェント相互作用における社会的因果関係と責任判断のモデル化
Social causality is the inference an entity makes about the social behavior of other entities and self. Besides physical cause and effect, social causality involves reasoning about epistemic states of agents and coercive circumstances. Based on such inference, responsibility judgment is the process whereby one singles out individuals to assign responsibility, credit or blame for multi-agent activities. Social causality and responsibility judgment are a key aspect of social intelligence, and a model for them facilitates the design and development of a variety of multi-agent interactive systems. Based on psychological attribution theory, this paper presents a domain-independent computational model to automate social inference and judgment process according to an agents causal knowledge and observations of interaction. We conduct experimental studies to empirically validate the computational model. The experimental results show that our model predicts human judgments of social attributions and makes inferences consistent with what most people do in their judgments. Therefore, the proposed model can be generically incorporated into an intelligent system to augment its social and cognitive functionality.
社会的因果関係とは、ある主体が他の主体および自己の社会的行動について行う推論です。物理的な因果関係に加え、社会的因果関係には、エージェントの認識論的状態や強制的な状況に関する推論が含まれます。このような推論に基づき、責任判断とは、マルチエージェント活動における責任、功績、または非難を個人に帰属させるプロセスです。社会的因果関係と責任判断は社会知能の重要な側面であり、それらのモデルは様々なマルチエージェントインタラクティブシステムの設計と開発を促進します。本稿では、心理学的帰属理論に基づき、エージェントの因果知識と相互作用の観察に基づいて社会的推論と判断プロセスを自動化する、ドメイン非依存の計算モデルを提示します。我々は、この計算モデルを実証的に検証するための実験研究を実施します。実験結果は、本モデルが人間の社会的帰属判断を予測し、ほとんどの人が判断において行うものと一致する推論を行うことを示しています。したがって、提案モデルは知能システムに汎用的に組み込むことができ、その社会的機能および認知機能を拡張することができます。
Improving Statistical Machine Translation for a Resource-Poor Language Using Related Resource-Rich Languages
関連リソース豊富な言語を用いたリソースの少ない言語の統計的機械翻訳の改善
We propose a novel language-independent approach for improving machine translation for resource-poor languages by exploiting their similarity to resource-rich ones. More precisely, we improve the translation from a resource-poor source language X_1 into a resource-rich language Y given a bi-text containing a limited number of parallel sentences for X_1-Y and a larger bi-text for X_2-Y for some resource-rich language X_2 that is closely related to X_1. This is achieved by taking advantage of the opportunities that vocabulary overlap and similarities between the languages X_1 and X_2 in spelling, word order, and syntax offer: (1) we improve the word alignments for the resource-poor language, (2) we further augment it with additional translation options, and (3) we take care of potential spelling differences through appropriate transliteration. The evaluation for Indonesian- >English using Malay and for Spanish -> English using Portuguese and pretending Spanish is resource-poor shows an absolute gain of up to 1.35 and 3.37 BLEU points, respectively, which is an improvement over the best rivaling approaches, while using much less additional data. Overall, our method cuts the amount of necessary “real” training data by a factor of 2–5.
リソースの乏しい言語とリソースが豊富な言語との類似性を活用することで、リソースの乏しい言語の機械翻訳を改善するための、言語に依存しない新しいアプローチを提案します。より正確には、限られた数の並列文を含むX_1-Yのバイテキストと、X_1に密接に関連するリソースが豊富な言語X_2のより大きなX_2-Yのバイテキストを与えられた場合に、リソースの乏しいソース言語X_1からリソースが豊富な言語Yへの翻訳を改善します。これは、言語X_1とX_2の語彙の重複と、綴り、語順、構文の類似性を活用することで実現されます。(1)リソースの乏しい言語の単語の対応を改善し、(2)追加の翻訳オプションでさらに拡張し、(3)適切な翻字によって潜在的な綴りの違いに対応します。マレー語を用いたインドネシア語→英語の評価、およびポルトガル語を用い、リソースの乏しいスペイン語を仮定したスペイン語→英語の評価では、それぞれ最大1.35と3.37のBLEUポイントの絶対的なゲインが示され、これは追加データの使用量を大幅に削減しながら、最良の競合アプローチよりも改善されています。全体として、この手法は必要な「実際の」トレーニングデータの量を2～5分の1に削減します。
Algorithms and Limits for Compact Plan Representations
コンパクトな計画表現のためのアルゴリズムと限界
Compact representations of objects is a common concept in computer science. Automated planning can be viewed as a case of this concept: a planning instance is a compact implicit representation of a graph and the problem is to find a path (a plan) in this graph. While the graphs themselves are represented compactly as planning instances, the paths are usually represented explicitly as sequences of actions. Some cases are known where the plans always have compact representations, for example, using macros. We show that these results do not extend to the general case, by proving a number of bounds for compact representations of plans under various criteria, like efficient sequential or random access of actions. In addition to this, we show that our results have consequences for what can be gained from reformulating planning into some other problem. As a contrast to this we also prove a number of positive results, demonstrating restricted cases where plans do have useful compact representations, as well as proving that macro plans have favourable access properties. Our results are finally discussed in relation to other relevant contexts.
オブジェクトのコンパクトな表現は、コンピュータサイエンスの一般的な概念です。自動プランニングはこの概念の例として考えることができます。プランニングインスタンスはグラフのコンパクトな暗黙的表現であり、問題はこのグラフ内のパス（プラン）を見つけることです。グラフ自体はプランニングインスタンスとしてコンパクトに表現されますが、パスは通常、アクションのシーケンスとして明示的に表現されます。マクロを使用するなど、プランが常にコンパクトな表現を持つケースがいくつか知られています。これらの結果は、アクションの効率的な順次アクセスやランダムアクセスなど、様々な基準の下でのプランのコンパクト表現の境界値をいくつか証明することにより、一般的なケースには適用できないことを示します。さらに、この結果は、プランニングを他の問題に再定式化することで得られる成果に影響を与えることを示します。これとは対照的に、プランが有用なコンパクト表現を持つ限定的なケースを実証し、マクロプランが好ましいアクセス特性を持つことを証明するなど、多くの肯定的な結果も証明します。最後に、他の関連するコンテキストとの関連で結果について説明します。
COLIN: Planning with Continuous Linear Numeric Change
COLIN：連続線形数値変化を伴う計画
In this paper we describe COLIN, a forward-chaining heuristic search planner, capable of reasoning with COntinuous LINear numeric change, in addition to the full temporal semantics of PDDL. Through this work we make two advances to the state-of-the-art in terms of expressive reasoning capabilities of planners: the handling of continuous linear change, and the handling of duration-dependent effects in combination with duration inequalities, both of which require tightly coupled temporal and numeric reasoning during planning. COLIN combines FF-style forward chaining search, with the use of a Linear Program (LP) to check the consistency of the interacting temporal and numeric constraints at each state. The LP is used to compute bounds on the values of variables in each state, reducing the range of actions that need to be considered for application. In addition, we develop an extension of the Temporal Relaxed Planning Graph heuristic of CRIKEY3, to support reasoning directly with continuous change. We extend the range of task variables considered to be suitable candidates for specifying the gradient of the continuous numeric change effected by an action. Finally, we explore the potential for employing mixed integer programming as a tool for optimising the timestamps of the actions in the plan, once a solution has been found. To support this, we further contribute a selection of extended benchmark domains that include continuous numeric effects. We present results for COLIN that demonstrate its scalability on a range of benchmarks, and compare to existing state-of-the-art planners.
本稿では、PDDLの完全な時間的セマンティクスに加え、連続線形数値変化による推論が可能な、前向き連鎖ヒューリスティック検索プランナーCOLINについて説明します。本研究を通して、プランナーの表現力豊かな推論機能に関して、最先端の2つの進歩を実現します。連続線形変化の処理、および期間不等式と組み合わせた期間依存効果の処理です。これらはどちらも、計画中に密に結合された時間的および数値的推論を必要とします。COLINは、FFスタイルの前向き連鎖検索と、線形計画(LP)を使用して各状態で相互作用する時間的制約と数値的制約の一貫性をチェックします。LPは、各状態の変数の値の境界を計算するために使用され、適用時に考慮する必要があるアクションの範囲を縮小します。さらに、連続変化による直接的な推論をサポートするために、CRIKEY3のTemporal Relaxed Planning Graphヒューリスティックの拡張を開発します。我々は、アクションによってもたらされる連続的な数値変化の勾配を指定するための適切な候補と考えられるタスク変数の範囲を拡張します。最後に、解が見つかった後、プラン内のアクションのタイムスタンプを最適化するツールとして混合整数計画法を適用する可能性を探ります。これをサポートするために、連続的な数値効果を含む拡張ベンチマークドメインの選択をさらに提供します。COLINの結果を提示し、さまざまなベンチマークでのスケーラビリティを実証し、既存の最先端のプランナーと比較します。