Journal of Artificial Intelligence Resarch: Volume 67の論文一覧

Journal of Artificial Intelligence Resarch Vol. 67 (2020)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。

論文

Best-First Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation

Best-First Enumeration Based on Bounding Conflicts, and its Application to Large-scale Hybrid Estimation / 境界衝突に基づくベストファースト列挙と大規模ハイブリッド推定への応用

There is an increasing desire for autonomous systems to have high levels of robustness and safety, attained through continuously planning and self-repairing online. Underlying this is the need to accurately estimate the system state and diagnose subtle failures. Estimation methods based on hybrid discrete and continuous state models have emerged as a method of precisely computing these estimates. However, existing methods have difficulty scaling to systems with more than a handful of components. Discrete, consistency based state estimation capabilities can scale to this level by combining best-first enumeration and conflict-directed search. While best-first methods have been developed for hybrid estimation, conflict-directed methods have thus far been elusive as conflicts learn inconsistencies from constraint violation, but probabilistic hybrid estimation is relatively unconstrained. In this paper we present an approach to hybrid estimation that unifies best-first enumeration and conflict-directed search through the concept of “bounding” conflicts, an extension of conflicts that represent tighter bounds on the cost of regions of the search space. This paper presents a general best-first enumeration algorithm based on bounding conflicts (A*BC) and a hybrid estimation method using this enumeration algorithm. Experiments show that an A*BC powered state estimator produces estimates up to an order of magnitude faster than the current state of the art, particularly on large systems.



自律システムには、継続的な計画とオンラインでの自己修復を通じて達成される高いレベルの堅牢性と安全性への要望が高まっています。その根底にあるのは、システム状態を正確に推定し、微妙な故障を診断する必要性です。離散状態モデルと連続状態モデルをハイブリッド化した推定手法は、これらの推定値を正確に計算する方法として登場しました。しかし、既存の手法は、少数のコンポーネントを超えるシステムへの拡張が困難です。離散的で一貫性に基づく状態推定機能は、最良優先列挙法と衝突指向探索法を組み合わせることで、このレベルまで拡張できます。最良優先手法はハイブリッド推定のために開発されてきましたが、衝突指向手法は、衝突が制約違反から不整合を学習するため、これまで実現が困難でした。一方、確率的ハイブリッド推定は比較的制約がありません。本稿では、探索空間の領域のコストに対するより厳しい境界を表す衝突の拡張である「境界付け」衝突の概念を用いて、最良優先列挙法と衝突指向探索を統合するハイブリッド推定手法を提示します。本論文では、境界衝突に基づく一般的なベストファースト列挙アルゴリズム（A*BC）と、この列挙アルゴリズムを用いたハイブリッド推定法を提示します。実験により、A*BCを用いた状態推定器は、特に大規模システムにおいて、現在の最先端技術よりも最大1桁高速に推定値を生成することが示されました。

Regret Bounds for Reinforcement Learning via Markov Chain Concentration

Regret Bounds for Reinforcement Learning via Markov Chain Concentration / マルコフ連鎖集中による強化学習の後悔境界

We give a simple optimistic algorithm for which it is easy to derive regret bounds of O(sqrt{t-mix SAT}) steps in uniformly ergodic Markov decision processes with S states, A actions, and mixing time parameter t-mix. These bounds are the first regret bounds in the general, non-episodic setting with an optimal dependence on all given parameters. They could only be improved by using an alternative mixing time parameter.



本論文では、S状態、A行動、および混合時間パラメータt-mixを持つ一様エルゴードマルコフ決定過程において、O(sqrt{t-mix SAT})ステップのリグレット境界を容易に導出できる、単純な楽観的アルゴリズムを提示します。これらの境界は、一般的な非エピソード設定において、すべての与えられたパラメータに最適な依存性を持つ初めてのリグレット境界です。これらの境界は、代替の混合時間パラメータを使用することによってのみ改善できます。

Saturated Cost Partitioning for Optimal Classical Planning

Saturated Cost Partitioning for Optimal Classical Planning / 最適古典的計画のための飽和コスト分割

Cost partitioning is a method for admissibly combining a set of admissible heuristic estimators by distributing operator costs among the heuristics. Computing an optimal cost partitioning, i.e., the operator cost distribution that maximizes the heuristic value, is often prohibitively expensive to compute. Saturated cost partitioning is an alternative that is much faster to compute and has been shown to yield high-quality heuristics. However, its greedy nature makes it highly susceptible to the order in which the heuristics are considered. We propose a greedy algorithm to generate orders and show how to use hill-climbing search to optimize a given order. Combining both techniques leads to significantly better heuristic estimates than using the best random order that is generated in the same time. Since there is often no single order that gives good guidance on the whole state space, we use the maximum of multiple orders as a heuristic that is significantly better informed than any single-order heuristic, especially when we actively search for a set of diverse orders.



コスト分割法は、オペレータコストをヒューリスティックスに分配することで、許容可能なヒューリスティック推定値の集合を許容的に組み合わせる手法です。最適なコスト分割法、すなわちヒューリスティック値を最大化するオペレータコスト分布の計算は、多くの場合、計算コストが法外に高くなります。飽和コスト分割法は、計算速度がはるかに速く、高品質のヒューリスティックスが得られることが示されている代替手法です。しかし、その貪欲な性質により、ヒューリスティックスが考慮される順序に大きく左右されます。本稿では、順序を生成する貪欲アルゴリズムを提案し、山登り探索を用いて与えられた順序を最適化する方法を示します。両方の手法を組み合わせることで、同時に生成される最良のランダム順序を用いる場合よりも、大幅に優れたヒューリスティック推定値が得られます。状態空間全体を適切に導く単一の順序は存在しないことが多いため、特に多様な順序の集合を積極的に探索する場合、単一順序のヒューリスティックスよりもはるかに情報に基づいたヒューリスティックとして、複数の順序の最大値を用います。

The Force Awakens: Artificial Intelligence for Consumer Law

The Force Awakens: Artificial Intelligence for Consumer Law / フォースの覚醒：消費者法のための人工知能

Recent years have been tainted by market practices that continuously expose us, as consumers, to new risks and threats. We have become accustomed, and sometimes even resigned, to businesses monitoring our activities, examining our data, and even meddling with our choices. Artificial Intelligence (AI) is often depicted as a weapon in the hands of businesses and blamed for allowing this to happen. In this paper, we envision a paradigm shift, where AI technologies are brought to the side of consumers and their organizations, with the aim of building an efficient and effective counter-power. AI-powered tools can support a massive-scale automated analysis of textual and audiovisual data, as well as code, for the benefit of consumers and their organizations. This in turn can lead to a better oversight of business activities, help consumers exercise their rights, and enable the civil society to mitigate information overload. We discuss the societal, political, and technological challenges that stand before that vision. This article is part of the special track on AI and Society.



近年、市場慣行は私たちを消費者として新たなリスクや脅威に絶えずさらしてきました。私たちは、企業が私たちの活動を監視し、データを調べ、さらには私たちの選択に干渉することに慣れてしまい、時には諦めさえしています。人工知能（AI）はしばしば企業の手に渡った武器として描かれ、このようなことが起こることを許していると非難されます。本稿では、AI技術を消費者とその組織の側に持ち込み、効率的で効果的な対抗力を構築するというパラダイムシフトを想定しています。AIを活用したツールは、消費者とその組織の利益のために、テキスト、オーディオビジュアルデータ、そしてコードの大規模な自動分析をサポートできます。これは、企業活動のより良い監視につながり、消費者が権利を行使するのを助け、市民社会が情報過多を軽減することを可能にします。私たちは、そのビジョンの前に立ちはだかる社会的、政治的、そして技術的な課題について議論します。この記事は、AIと社会に関する特別トラックの一部です。

Blind Spot Detection for Safe Sim-to-Real Transfer

Blind Spot Detection for Safe Sim-to-Real Transfer / 安全なシミュレーションから現実への転送のための死角検出

Agents trained in simulation may make errors when performing actions in the real world due to mismatches between training and execution environments. These mistakes can be dangerous and difficult for the agent to discover because the agent is unable to predict them a priori. In this work, we propose the use of oracle feedback to learn a predictive model of these blind spots in order to reduce costly errors in real-world applications. We focus on blind spots in reinforcement learning (RL) that occur due to incomplete state representation: when the agent lacks necessary features to represent the true state of the world, and thus cannot distinguish between numerous states. We formalize the problem of discovering blind spots in RL as a noisy supervised learning problem with class imbalance. Our system learns models for predicting blind spots within unseen regions of the state space by combining techniques for label aggregation, calibration, and supervised learning. These models take into consideration noise emerging from different forms of oracle feedback, including demonstrations and corrections.We evaluate our approach across two domains and demonstrate that it achieves higher predictive performance than baseline methods, and also that the learned model can be used to selectively query an oracle at execution time to prevent errors. We also empirically analyze the biases of various feedback types and how these biases influence the discovery of blind spots. Further, we include analyses of our approach that incorporate relaxed initial optimality assumptions. (Interestingly, relaxing the assumptions of an optimal oracle and an optimal simulator policy helped our models to perform better.) We also propose extensions to our method that are intended to improve performance when using corrections and demonstrations data.



シミュレーションで訓練されたエージェントは、訓練環境と実行環境の不一致により、現実世界での行動実行時にエラーを犯す可能性があります。エージェントは事前にこれらのミスを予測できないため、これらのミスは危険であり、エージェントが発見することが困難です。この研究では、現実世界のアプリケーションでコストのかかるエラーを削減するために、オラクル フィードバックを使用してこれらの盲点の予測モデルを学習することを提案します。私たちは、不完全な状態表現によって発生する強化学習(RL)の盲点に焦点を当てています。つまり、エージェントが世界の真の状態を表現するために必要な特徴を欠いており、多数の状態を区別できない場合です。私たちは、RLで盲点を発見する問題を、クラスの不均衡を伴うノイズの多い教師あり学習問題として形式化します。私たちのシステムは、ラベル集約、キャリブレーション、教師あり学習の手法を組み合わせることで、状態空間の見えない領域内の盲点を予測するモデルを学習します。これらのモデルは、デモンストレーションや修正を含む様々な形式のオラクルフィードバックから生じるノイズを考慮に入れています。2つの領域にわたってこのアプローチを評価し、ベースライン手法よりも高い予測性能を達成すること、そして学習済みモデルを用いて実行時にオラクルを選択的にクエリすることでエラーを防止できることを実証しました。また、様々なフィードバックタイプのバイアスと、これらのバイアスが盲点の発見にどのように影響するかを実証的に分析しました。さらに、初期最適性仮定を緩和したアプローチの分析も行っています。（興味深いことに、最適なオラクルと最適なシミュレータポリシーの仮定を緩和することで、モデルのパフォーマンスが向上しました。）また、修正データとデモンストレーションデータを使用する際のパフォーマンスを向上させることを目的とした、この手法の拡張も提案しています。

Planning for Hybrid Systems via Satisfiability Modulo Theories

Planning for Hybrid Systems via Satisfiability Modulo Theories / 充足可能性モジュロ理論によるハイブリッドシステムの計画

Planning for hybrid systems is important for dealing with real-world applications, and PDDL+ supports this representation of domains with mixed discrete and continuous dynamics. In this paper we present a new approach for planning for hybrid systems, based on encoding the planning problem as a Satisfiability Modulo Theories (SMT) formula. This is the first SMT encoding that can handle the whole set of PDDL+ features (including processes and events), and is implemented in the planner SMTPlan. SMTPlan not only covers the full semantics of PDDL+, but can also deal with non-linear polynomial continuous change without discretization. This allows it to generate plans with non-linear dynamics that are correct-by-construction. The encoding is based on the notion of happenings, and can be applied on domains with nonlinear continuous change. We describe the encoding in detail and provide in-depth examples. We apply this encoding in an iterative deepening planning algorithm. Experimental results show that the approach dramatically outperforms existing work in finding plans for PDDL+ problems. We also present experiments which explore the performance of the proposed approach on temporal planning problems, showing that the scalability of the approach is limited by the size of the discrete search space. We further extend the encoding to include planning with control parameters. The extended encoding allows the definition of actions to include infinite domain parameters, called control parameters. We present experiments on a set of problems with control parameters to demonstrate the positive effect they provide to the approach of planning via SMT.



ハイブリッドシステムのプランニングは、現実世界のアプリケーションを扱う上で重要であり、PDDL+は離散型と連続型のダイナミクスが混在するドメインの表現をサポートしています。本稿では、プランニング問題を充足可能性モジュロ理論（SMT）式としてエンコードすることに基づく、ハイブリッドシステムのプランニングのための新しいアプローチを紹介します。これは、PDDL+の機能全体（プロセスとイベントを含む）を扱うことができる初のSMTエンコードであり、プランナーSMTPlanに実装されています。SMTPlanはPDDL+の完全なセマンティクスをカバーするだけでなく、離散化なしで非線形多項式連続変化を扱うことができます。これにより、非線形ダイナミクスを持つプランを、構成時に正しく生成することが可能になります。このエンコードは出来事の概念に基づいており、非線形連続変化を持つドメインに適用できます。本稿ではエンコードについて詳細に説明し、詳細な例を示します。このエンコードを反復深化プランニングアルゴリズムに適用します。実験結果から、このアプローチはPDDL+の問題に対するプランニングにおいて、既存の研究を大幅に上回る性能を示すことが示されました。また、提案手法のテンポラルプランニング問題に対する性能を調査する実験も示し、この手法のスケーラビリティは離散探索空間のサイズによって制限されることを示します。さらに、制御パラメータを用いたプランニングを含めるようにエンコーディングを拡張します。拡張されたエンコーディングにより、アクションの定義に制御パラメータと呼ばれる無限のドメインパラメータを含めることができます。制御パラメータを含む一連の問題に対する実験を示し、SMTを介したプランニング手法に制御パラメータがもたらすプラスの効果を示します。

TensorLog: A Probabilistic Database Implemented Using Deep-Learning Infrastructure

TensorLog: A Probabilistic Database Implemented Using Deep-Learning Infrastructure / TensorLog：ディープラーニング基盤を用いて実装された確率データベース

We present an implementation of a probabilistic first-order logic called TensorLog, in which classes of logical queries are compiled into differentiable functions in a neural-network infrastructure such as Tensorflow or Theano. This leads to a close integration of probabilistic logical reasoning with deep-learning infrastructure: in particular, it enables high-performance deep learning frameworks to be used for tuning the parameters of a probabilistic logic. The integration with these frameworks enables use of GPU-based parallel processors for inference and learning, making TensorLog the first highly parallellizable probabilistic logic. Experimental results show that TensorLog scales to problems involving hundreds of thousands of knowledge-base triples and tens of thousands of examples.



TensorLogと呼ばれる確率的一階述語論理の実装を示します。これは、論理クエリのクラスをTensorflowやTheanoなどのニューラルネットワークインフラストラクチャ内の微分可能な関数にコンパイルします。これにより、確率的論理推論とディープラーニングインフラストラクチャが緊密に統合されます。特に、確率的論理のパラメータを調整するために高性能ディープラーニングフレームワークを使用できるようになります。これらのフレームワークとの統合により、推論と学習にGPUベースの並列プロセッサを使用できるようになり、TensorLogは高度に並列化可能な最初の確率的論理となります。実験結果から、TensorLogは数十万の知識ベーストリプルと数万の例を含む問題にスケールすることが示されています。

Jointly Improving Parsing and Perception for Natural Language Commands through Human-Robot Dialog

Jointly Improving Parsing and Perception for Natural Language Commands through Human-Robot Dialog / 人間とロボットの対話による自然言語コマンドの構文解析と知覚の共同改善

In this work, we present methods for using human-robot dialog to improve language understanding for a mobile robot agent. The agent parses natural language to underlying semantic meanings and uses robotic sensors to create multi-modal models of perceptual concepts like red and heavy. The agent can be used for showing navigation routes, delivering objects to people, and relocating objects from one location to another. We use dialog clari_cation questions both to understand commands and to generate additional parsing training data. The agent employs opportunistic active learning to select questions about how words relate to objects, improving its understanding of perceptual concepts. We evaluated this agent on Amazon Mechanical Turk. After training on data induced from conversations, the agent reduced the number of dialog questions it asked while receiving higher usability ratings. Additionally, we demonstrated the agent on a robotic platform, where it learned new perceptual concepts on the y while completing a real-world task.



本研究では、人間とロボットの対話を用いて移動ロボットエージェントの言語理解を向上させる手法を提示します。エージェントは自然言語を根底にある意味まで解析し、ロボットセンサーを用いて「赤」や「重い」といった知覚概念のマルチモーダルモデルを作成します。このエージェントは、ナビゲーションルートの表示、人への物体の配達、物体をある場所から別の場所への移動に使用できます。コマンドの理解と追加の解析トレーニングデータの生成の両方に、対話の明確化質問を使用します。エージェントは、単語と物体の関係に関する質問を選択するために、機会主義的能動学習を採用し、知覚概念の理解を向上させます。このエージェントをAmazon Mechanical Turkで評価しました。会話から誘導されたデータでトレーニングした後、エージェントは対話質問の数を減らし、より高いユーザビリティ評価を獲得しました。さらに、ロボットプラットフォーム上でエージェントのデモを行い、実世界のタスクを完了しながら新しい知覚概念を学習しました。

The Impact of Treewidth on Grounding and Solving of Answer Set Programs

The Impact of Treewidth on Grounding and Solving of Answer Set Programs / インパクトツリー幅が解集合プログラムのグラウンディングと解法に与える影響

In this paper, we aim to study how the performance of modern answer set programming (ASP) solvers is influenced by the treewidth of the input program and to investigate the consequences of this relationship. We first perform an experimental evaluation that shows that the solving performance is heavily influenced by treewidth, given ground input programs that are otherwise uniform, both in size and construction. This observation leads to an important question for ASP, namely, how to design encodings such that the treewidth of the resulting ground program remains small. To this end, we study two classes of disjunctive programs, namely guarded and connection-guarded programs. In order to investigate these classes, we formalize the grounding process using MSO transductions. Our main results show that both classes guarantee that the treewidth of the program after grounding only depends on the treewidth (and the maximum degree, in case of connection-guarded programs) of the input instance. In terms of parameterized complexity, our findings yield corresponding FPT results for answer-set existence for bounded treewidth (and also degree, for connection-guarded programs) of the input instance. We further show that bounding treewidth alone leads to NP-hardness in the data complexity for connection-guarded programs, which indicates that the two classes are fundamentally different. Finally, we show that for both classes, the data complexity remains as hard as in the general case of ASP.



本稿では、現代の解答セットプログラミング(ASP)ソルバーのパフォーマンスが入力プログラムのツリー幅によってどのように影響を受けるかを調べ、この関係の帰結を調査することを目的としています。まず、サイズと構成の両方において均一な基底入力プログラムを与えられた場合、解決パフォーマンスはツリー幅に大きく影響されることを示す実験的評価を行います。この観察は、ASPにとって重要な問題、すなわち、結果として得られる基底プログラムのツリー幅が小さくなるようにエンコーディングを設計する方法につながります。この目的のために、ガード付きプログラムと接続ガード付きプログラムの2つのクラスの選言プログラムを調査します。これらのクラスを調査するために、MSOトランスダクションを使用して基底処理を形式化します。主な結果は、両方のクラスで、基底処理後のプログラムのツリー幅が入力インスタンスのツリー幅(および接続ガード付きプログラムの場合は最大次数)のみに依存することを保証することを示しています。パラメータ化された複雑性に関して、我々の調査結果は、入力インスタンスの制限された木幅（および接続保護されたプログラムの場合は次数）に対する解答集合の存在について、対応するFPT結果をもたらします。さらに、木幅を制限するだけで、接続保護されたプログラムのデータ複雑性がNP困難になることを示し、これは2つのクラスが根本的に異なることを示しています。最後に、両方のクラスについて、データ複雑性がASPの一般的な場合と同じくらい難しいままであることを示します。

Adversarial Attacks on Crowdsourcing Quality Control

Adversarial Attacks on Crowdsourcing Quality Control / クラウドソーシング品質管理に対する敵対的攻撃

Crowdsourcing is a popular methodology to collect manual labels at scale. Such labels are often used to train AI models and, thus, quality control is a key aspect in the process. One of the most popular quality assurance mechanisms in paid micro-task crowdsourcing is based on gold questions: the use of a small set of tasks of which the requester knows the correct answer and, thus, is able to directly assess crowd work quality. In this paper, we show that such mechanism is prone to an attack carried out by a group of colluding crowd workers that is easy to implement and deploy: the inherent size limit of the gold set can be exploited by building an inferential system to detect which parts of the job are more likely to be gold questions. The described attack is robust to various forms of randomisation and programmatic generation of gold questions. We present the architecture of the proposed system, composed of a browser plug-in and an external server used to share information, and briefly introduce its potential evolution to a decentralised implementation. We implement and experimentally validate the gold detection system, using real-world data from a popular crowdsourcing platform.  Our experimental results show that crowdworkers using the proposed system spend more time on signalled gold questions but do not neglect the others thus achieving an increased overall work quality. Finally, we discuss the economic and sociological implications of this kind of attack.



クラウドソーシングは、大規模に手動ラベルを収集するための一般的な手法です。このようなラベルはAIモデルのトレーニングによく使用されるため、品質管理はプロセスの重要な側面です。有料のマイクロタスク クラウドソーシングで最も人気のある品質保証メカニズムの1つは、ゴールド クエスチョンに基づいています。これは、依頼者が正しい答えを知っている少数のタスク セットを使用するため、クラウド ワークの品質を直接評価できます。本稿では、このようなメカニズムは、共謀するクラウドワーカーのグループによって実行される、実装と展開が容易な攻撃を受けやすいことを示します。つまり、ゴールドセットの固有のサイズ制限は、仕事のどの部分がゴールドの質問である可能性が高いかを検出する推論システムを構築することによって悪用できます。説明した攻撃は、さまざまな形式のランダム化とゴールドの質問のプログラムによる生成に対して堅牢です。ブラウザプラグインと情報共有に使用される外部サーバーで構成された提案システムのアーキテクチャを示し、分散実装への潜在的な進化を簡単に紹介します。人気のあるクラウドソーシングプラットフォームの実際のデータを使用して、ゴールド検出システムを実装し、実験的に検証します。実験結果によると、提案システムを使用するクラウドワーカーは、シグナルされたゴールドの質問に多くの時間を費やしますが、他の質問を無視することはないため、全体的な作業品質が向上します。最後に、この種の攻撃の経済的および社会学的な意味合いについて説明します。

Graph Width Measures for CNF-Encodings with Auxiliary Variables

Graph Width Measures for CNF-Encodings with Auxiliary Variables / 補助変数を含むCNFエンコーディングのグラフ幅測定

We consider bounded width CNF-formulas where the width is measured by popular graph width measures on graphs associated to CNF-formulas. Such restricted graph classes, in particular those of bounded treewidth, have been extensively studied for their uses in the design of algorithms for various computational problems on CNF-formulas. Here we consider the expressivity of these formulas in the model of clausal encodings with auxiliary variables. We first show that bounding the width for many of the measures from the literature leads to a dramatic loss of expressivity, restricting the formulas to such of low communication complexity. We then show that the width of optimal encodings with respect to different measures is strongly linked: there are two classes of width measures, one containing primal treewidth and the other incidence cliquewidth, such that in each class the width of optimal encodings only differs by constant factors. Moreover, between the two classes the width differs at most by a factor logarithmic in the number of variables. Both these results are in stark contrast to the setting without auxiliary variables where all width measures we consider here differ by more than constant factors and in many cases even by linear factors.



我々は、CNF式に関連付けられたグラフ上の一般的なグラフ幅の尺度によって幅が測定される、制限された幅のCNF式を考察します。このような制限されたグラフクラス、特に制限された木幅のグラフクラスは、CNF式に関するさまざまな計算問題に対するアルゴリズムの設計における使用について広く研究されてきた。ここでは、補助変数を含む節符号化モデルにおけるこれらの式の表現力を考察します。まず、文献の多くの尺度の幅を制限すると表現力が劇的に低下し、通信の複雑さが低い式に制限されることを示す。次に、異なる尺度に関する最適な符号化の幅は強く結びついていることを示す。幅の尺度には2つのクラスがあり、1つは主木幅を含み、もう1つは発生クリーク幅を含む。各クラスでは、最適な符号化の幅は定数倍のみ異なります。さらに、2つのクラス間では、幅は最大で変数の数の対数倍しか異なることはない。これらの結果はいずれも、ここで検討するすべての幅の尺度が定数倍以上、多くの場合線形倍数で異なる補助変数なしの設定とは著しく対照的です。

Catching Cheats: Detecting Strategic Manipulation in Distributed Optimisation of Electric Vehicle Aggregators

Catching Cheats: Detecting Strategic Manipulation in Distributed Optimisation of Electric Vehicle Aggregators / チートの捕捉：電気自動車アグリゲータの分散最適化における戦略的操作の検出

Given the rapid rise of electric vehicles (EVs) worldwide, and the ambitious targets set for the near future, the management of large EV fleets must be seen as a priority. Specifically, we study a scenario where EV charging is managed through self-interested EV aggregators who compete in the day-ahead market in order to purchase the electricity needed to meet their clients’ requirements. With the aim of reducing electricity costs and lowering the impact on electricity markets, a centralised bidding coordination framework has been proposed in the literature employing a coordinator. In order to improve privacy and limit the need for the coordinator, we propose a reformulation of the coordination framework as a decentralised algorithm, employing the Alternating Direction Method of Multipliers (ADMM). However, given the self-interested nature of the aggregators, they can deviate from the algorithm in order to reduce their energy costs. Hence, we study the strategic manipulation of the ADMM algorithm and, in doing so, describe and analyse different possible attack vectors and propose a mathematical framework to quantify and detect manipulation. Importantly, this detection framework is not limited to the considered EV scenario and can be applied to general ADMM algorithms. Finally, we test the proposed decentralised coordination and manipulation detection algorithms in realistic scenarios using real market and driver data from Spain. Our empirical results show that the decentralised algorithm’s convergence to the optimal solution can be effectively disrupted by manipulative attacks achieving convergence to a different non-optimal solution which benefits the attacker. With respect to the detection algorithm, results indicate that it achieves very high accuracies and significantly outperforms a naive benchmark.



世界中で電気自動車（EV）が急速に普及し、近い将来に野心的な目標が設定されていることを考えると、大規模なEVフリートの管理は優先事項として捉えなければならない。具体的には、顧客の需要を満たすために必要な電力を購入するために前日市場で競争する、利己的なEVアグリゲーターを通じてEV充電が管理されるシナリオを検討します。電力コストを削減し、電力市場への影響を軽減することを目的として、文献ではコーディネーターを用いた集中型入札調整フレームワークが提案されています。プライバシーを向上させ、コーディネーターの必要性を制限するために、我々は交互方向乗数法（ADMM）を用いた分散型アルゴリズムとして調整フレームワークを再定式化することを提案します。しかし、アグリゲーターの利己的な性質を考慮すると、彼らはエネルギーコストを削減するためにアルゴリズムから逸脱する可能性があります。そこで、我々はADMMアルゴリズムの戦略的操作を研究し、その際に、考えられるさまざまな攻撃ベクトルを記述・分析し、操作を定量化して検出するための数学的フレームワークを提案します。重要なことは、この検出フレームワークは検討されているEVシナリオに限定されず、一般的なADMMアルゴリズムに適用できることです。最後に、スペインの実際の市場とドライバーデータを使用して、現実的なシナリオで提案された分散型調整および操作検出アルゴリズムをテストします。我々の実験結果は、分散型アルゴリズムの最適解への収束は、攻撃者に利益をもたらす別の非最適解への収束を達成する操作攻撃によって効果的に妨害される可能性があることを示しています。検出アルゴリズムに関しては、結果は非常に高い精度を達成し、単純なベンチマークを大幅に上回ることを示しています。

Fair Allocation with Diminishing Differences

Fair Allocation with Diminishing Differences / 差が減少する公平な割り当て

Ranking alternatives is a natural way for humans to explain their preferences. It is used in many settings, such as school choice, course allocations and residency matches. Without having any information on the underlying cardinal utilities, arguing about the fairness of allocations requires extending the ordinal item ranking to ordinal bundle ranking. The most commonly used such extension is stochastic dominance (SD), where a bundle X is preferred over a bundle Y if its score is better according to all additive score functions. SD is a very conservative extension, by which few allocations are necessarily fair while many allocations are possibly fair. We propose to make a natural assumption on the underlying cardinal utilities of the players, namely that the difference between two items at the top is larger than the difference between two items at the bottom. This assumption implies a preference extension which we call diminishing differences (DD), where X is preferred over Y if its score is better according to all additive score functions satisfying the DD assumption. We give a full characterization of allocations that are necessarily-proportional or possibly-proportional according to this assumption. Based on this characterization, we present a polynomial-time algorithm for finding a necessarily-DD-proportional allocation whenever it exists. Using simulations, we compare the various fairness criteria in terms of their probability of existence, and their probability of being fair by the underlying cardinal valuations. We find that necessary-DD-proportionality fares well in both measures. We also consider envy-freeness and Pareto optimality under diminishing-differences, as well as chore allocation under the analogous condition — increasing-differences.



選択肢の順位付けは、人間が自らの選好を説明する自然な方法です。これは、学校選択、コース配分、居住地マッチングなど、多くの場面で用いられています。根本的な基数効用に関する情報がない場合、配分の公平性を議論するには、順序付けアイテム順位付けを順序付けバンドル順位付けに拡張する必要があります。最も一般的に用いられる拡張は確率的優位性（SD）であり、バンドルXは、すべての加法スコア関数に従ってスコアが優れている場合、バンドルYよりも好まれます。SDは非常に保守的な拡張であり、必然的に公平となる配分は少ないが、多くの配分はおそらく公平となります。我々は、プレイヤーの根本的な基数効用に関して自然な仮定、すなわち、上位2つのアイテム間の差は下位2つのアイテム間の差よりも大きいという仮定を立てることを提案します。この仮定は、逓減差（DD）と呼ぶ選好拡張を意味します。DD仮定を満たすすべての加法スコア関数に従ってスコアが優れている場合、XはYよりも好まれます。この仮定に基づいて、必然的に比例する、あるいはおそらく比例する配分の完全な特徴づけを行う。この特徴づけに基づき、必然的に比例する配分が存在する場合には、それを常に検出するための多項式時間アルゴリズムを提示します。シミュレーションを用いて、様々な公平性基準を、その存在確率と、基礎となる基数評価による公平性の確率の観点から比較します。必然的に比例する配分は、どちらの尺度においても良好な結果を示すことが分かった。また、漸減差異下における羨望のなさおよびパレート最適性、そして類似の条件である漸増差異下における雑用配分についても考察します。

A Global Constraint for the Exact Cover Problem: Application to Conceptual Clustering

A Global Constraint for the Exact Cover Problem: Application to Conceptual Clustering / 完全被覆問題に対する大域的制約：概念クラスタリングへの応用

We introduce the exactCover global constraint dedicated to the exact cover problem, the goal of which is to select subsets such that each element of a given set belongs to exactly one selected subset. This NP-complete problem occurs in many applications, and we more particularly focus on a conceptual clustering application.We introduce three propagation algorithms for exactCover, called Basic, DL, and DL+: Basic ensures the same level of consistency as arc consistency on a classical decomposition of exactCover into binary constraints, without using any specific data structure; DL ensures the same level of consistency as Basic but uses Dancing Links to efficiently maintain the relation between elements and subsets; and DL+ is a stronger propagator which exploits an extra property to filter more values than DL.We also consider the case where the number of selected subsets is constrained to be equal to a given integer variable k, and we show that this may be achieved either by combining exactCover with existing constraints, or by designing a specific propagator that integrates algorithms designed for the NValues constraint.These different propagators are experimentally evaluated on conceptual clustering problems, and they are compared with state-of-the-art declarative approaches. In particular, we show that our global constraint is competitive with recent ILP and CP models for mono-criterion problems, and it has better scale-up properties for multi-criteria problems.



与えられた集合の各要素が、選択された1つの部分集合にのみ属するように部分集合を選択することを目的とする、完全被覆問題専用のexactCoverグローバル制約を導入します。このNP完全問題は多くのアプリケーションで発生しますが、ここでは特に概念クラスタリング アプリケーションに焦点を当てます。exactCoverの3つの伝播アルゴリズム(Basic、DL、DL+)を紹介します。Basicは、特定のデータ構造を使用せずに、exactCoverをバイナリ制約に古典的に分解した場合のアーク一貫性と同じレベルの一貫性を保証します。DLはBasicと同じレベルの一貫性を保証しますが、Dancing Linksを使用して要素とサブセットの関係を効率的に維持します。DL+は、追加のプロパティを利用してDLより多くの値をフィルターする、より強力な伝播器です。また、選択されたサブセットの数が特定の整数変数kと等しくなるように制約される場合を考慮し、exactCoverを既存の制約と組み合わせるか、NValues制約用に設計されたアルゴリズムを統合する特定の伝播器を設計することによってこれを実現できることを示します。これらの異なる伝播器は概念クラスタリングの問題で実験的に評価され、最先端の宣言的アプローチと比較されます。特に、提案するグローバル制約は、単一基準問題において最近のILPおよびCPモデルと競合可能であり、複数基準問題においてより優れたスケールアップ特性を持つことを示す。

Robust Multi-Agent Path Finding and Executing

Robust Multi-Agent Path Finding and Executing / ロバストなマルチエージェント経路探索と実行

Multi-agent path-finding (MAPF) is the problem of finding a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. In this work, we propose a holistic solution for MAPF that is robust to such unexpected delays. First, we introduce the notion of a k-robust MAPF plan, which is a plan that can be executed even if a limited number (k) of delays occur. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we propose several robust execution policies. An execution policy is a policy for agents executing a MAPF plan. An execution policy is robust if following it guarantees that the agents reach their goals even if they encounter unexpected delays. Several classes of such robust execution policies are proposed and evaluated experimentally. Finally, we present robust execution policies for cases where communication between the agents may also be delayed. We performed an extensive experimental evaluation in which we compared different algorithms for finding robust MAPF plans, compared different ro- bust execution policies, and studied the interplay between having a robust plan and the performance when using a robust execution policy.



マルチエージェント経路探索（MAPF）は、エージェント群を初期位置から目標地点まで衝突なく移動させるための計画を求める問題です。しかし、予期せぬイベントによって一部のエージェントが遅延するため、この計画に従うことが不可能となる場合があります。本研究では、このような予期せぬ遅延に対して堅牢なMAPFの包括的解法を提案します。まず、k-ロバストMAPF計画の概念を導入します。これは、限られた数（k）の遅延が発生しても実行可能な計画です。k-ロバスト計画を見つけるための十分条件と必要条件を提案し、そのような計画を見つけるために複数のMAPFソルバーを変換する方法を示す。次に、いくつかの堅牢な実行ポリシーを提案します。実行ポリシーとは、エージェントがMAPF計画を実行するためのポリシーです。実行ポリシーが堅牢であるのは、それに従うことで、予期せぬ遅延に遭遇した場合でもエージェントが目標地点に到達することが保証される場合です。このような堅牢な実行ポリシーのいくつかのクラスが提案され、実験的に評価されています。最後に、エージェント間の通信が遅延する可能性のある場合の堅牢な実行ポリシーを提示します。堅牢なMAPFプランを見つけるためのさまざまなアルゴリズム、さまざまな堅牢な実行ポリシーを比較し、堅牢なプランを持つことと堅牢な実行ポリシーを使用した場合のパフォーマンスとの相互作用を調査する、広範な実験評価を実施しました。

Agreement on Target-Bidirectional Recurrent Neural Networks for Sequence-to-Sequence Learning

Agreement on Target-Bidirectional Recurrent Neural Networks for Sequence-to-Sequence Learning / シーケンスツーシーケンス学習のためのターゲット双方向リカレントニューラルネットワークに関する合意

Recurrent neural networks are extremely appealing for sequence-to-sequence learning tasks. Despite their great success, they typically suffer from a shortcoming: they are prone to generate unbalanced targets with good prefixes but bad suffixes, and thus performance suffers when dealing with long sequences. We propose a simple yet effective approach to overcome this shortcoming. Our approach relies on the agreement between a pair of target-directional RNNs, which generates more balanced targets. In addition, we develop two efficient approximate search methods for agreement that are empirically shown to be almost optimal in terms of either sequence level or non-sequence level metrics. Extensive experiments were performed on three standard sequence-to-sequence transduction tasks: machine transliteration, grapheme-to-phoneme transformation and machine translation. The results show that the proposed approach achieves consistent and substantial improvements, compared to many state-of-the-art systems.



リカレントニューラルネットワークは、シーケンス間学習タスクにおいて非常に魅力的です。しかし、その大きな成功にもかかわらず、一般的に欠点があります。それは、良い接頭辞を持つが悪い接尾辞を持つアンバランスなターゲットを生成する傾向があり、そのため長いシーケンスを処理する際にパフォーマンスが低下することです。私たちは、この欠点を克服するためのシンプルかつ効果的なアプローチを提案します。私たちのアプローチは、よりバランスの取れたターゲットを生成する一対のターゲット指向性RNN間の一致に依存しています。さらに、私たちは、シーケンスレベルまたは非シーケンスレベルのメトリクスのいずれかに関して、ほぼ最適であることが経験的に示された、一致のための2つの効率的な近似探索法を開発しました。機械翻字、書記素から音素への変換、機械翻訳という3つの標準的なシーケンス間変換タスクについて、広範な実験が行われました。その結果、提案されたアプローチは、多くの最先端システムと比較して、一貫して大幅な改善を達成することがわかりました。

Solving Delete Free Planning with Relaxed Decision Diagram Based Heuristics

Solving Delete Free Planning with Relaxed Decision Diagram Based Heuristics / 緩和決定図に基づくヒューリスティックを用いた削除フリープランニングの解決

We investigate the use of relaxed decision diagrams (DDs) for computing admissible heuristics for the cost-optimal delete-free planning (DFP) problem. Our main contributions are the introduction of two novel DD encodings for a DFP task: a multivalued decision diagram that includes the sequencing aspect of the problem and a binary decision diagram representation of its sequential relaxation. We present construction algorithms for each DD that leverage these different perspectives of the DFP task and provide theoretical and empirical analyses of the associated heuristics. We further show that relaxed DDs can be used beyond heuristic computation to extract delete-free plans, find action landmarks, and identify redundant actions. Our empirical analysis shows that while DD-based heuristics trail the state of the art, even small relaxed DDs are competitive with the linear programming heuristic for the DFP task, thus, revealing novel ways of designing admissible heuristics.



我々は、コスト最適削除フリープランニング（DFP）問題に対する許容ヒューリスティックを計算するための緩和決定図（DD）の使用を調査します。我々の主な貢献は、DFPタスク用の2つの新しいDDエンコーディング、すなわち問題の順序付けの側面を含む多値決定図と、その順序付け緩和のバイナリ決定図表現の導入です。我々は、DFPタスクのこれらの異なる観点を活用する各DDの構築アルゴリズムを提示し、関連するヒューリスティックの理論的および実証的分析を提供します。さらに、緩和DDはヒューリスティック計算を超えて、削除フリープランの抽出、アクションランドマークの検出、冗長アクションの識別に使用できることを示します。我々の実証的分析は、DDベースのヒューリスティックは最先端技術に遅れをとっているものの、小さな緩和DDであってもDFPタスクの線形計画法ヒューリスティックと競合できることを示しており、許容ヒューリスティックを設計する新しい方法を明らかにしています。

A Set of Recommendations for Assessing Human–Machine Parity in Language Translation

A Set of Recommendations for Assessing Human–Machine Parity in Language Translation / 言語翻訳における人間と機械の同等性を評価するための一連の推奨事項

The quality of machine translation has increased remarkably over the past years, to the degree that it was found to be indistinguishable from professional human translation in a number of empirical investigations. We reassess Hassan et al.’s 2018 investigation into Chinese to English news translation, showing that the finding of human–machine parity was owed to weaknesses in the evaluation design—which is currently considered best practice in the field. We show that the professional human translations contained significantly fewer errors, and that perceived quality in human evaluation depends on the choice of raters, the availability of linguistic context, and the creation of reference translations. Our results call for revisiting current best practices to assess strong machine translation systems in general and human–machine parity in particular, for which we offer a set of recommendations based on our empirical findings.



機械翻訳の品質はここ数年で著しく向上し、多くの実証調査でプロの人間による翻訳と区別がつかないほどになっています。私たちは、Hassanらによる2018年の中国語から英語へのニュース翻訳の調査を再評価し、人間と機械が同等であるという結果は、現在この分野のベストプラクティスと考えられている評価設計の弱点によるものであることを示しています。プロの人間による翻訳には有意に少ないエラーが含まれており、人間による評価で認識される品質は、評価者の選択、言語的コンテキストの利用可能性、および参照翻訳の作成に依存することを示しています。私たちの結果は、一般的な強力な機械翻訳システム、特に人間と機械の同等性を評価するために、現在のベストプラクティスを再検討することを要求しており、私たちは実証的調査結果に基づいて一連の推奨事項を提示しています。

Using Task Descriptions in Lifelong Machine Learning for Improved Performance and Zero-Shot Transfer

Using Task Descriptions in Lifelong Machine Learning for Improved Performance and Zero-Shot Transfer / 生涯機械学習におけるタスク記述を用いたパフォーマンス向上とゼロショット転移

Knowledge transfer between tasks can improve the performance of learned models, but requires an accurate estimate of inter-task relationships to identify the relevant knowledge to transfer. These inter-task relationships are typically estimated based on training data for each task, which is inefficient in lifelong learning settings where the goal is to learn each consecutive task rapidly from as little data as possible. To reduce this burden, we develop a lifelong learning method based on coupled dictionary learning that utilizes high-level task descriptions to model inter-task relationships. We show that using task descriptors improves the performance of the learned task policies, providing both theoretical justification for the benefit and empirical demonstration of the improvement across a variety of learning problems. Given only the descriptor for a new task, the lifelong learner is also able to accurately predict a model for the new task through zero-shot learning using the coupled dictionary, eliminating the need to gather training data before addressing the task.



タスク間の知識転送は学習したモデルのパフォーマンスを向上させることができますが、転送する関連知識を特定するためにタスク間の関係を正確に推定する必要があります。これらのタスク間の関係は通常、各タスクのトレーニング データに基づいて推定されますが、可能な限り少ないデータから各連続タスクを迅速に学習することを目標とする生涯学習の設定では非効率的です。この負担を軽減するために、高レベルのタスク記述を使用してタスク間の関係をモデル化する、結合辞書学習に基づく生涯学習手法を開発しました。タスク記述子を使用すると、学習したタスク ポリシーのパフォーマンスが向上することが示され、利点の理論的根拠と、さまざまな学習問題にわたる改善の実証的デモンストレーションの両方が提供されます。新しいタスクの記述子のみが与えられた場合、生涯学習者は結合辞書を使用したゼロ ショット学習を通じて新しいタスクのモデルを正確に予測できるため、タスクに対処する前にトレーニング データを収集する必要がなくなります。

Hedonic Games with Ordinal Preferences and Thresholds

Hedonic Games with Ordinal Preferences and Thresholds / 順序選好と閾値を用いた快楽ゲーム

We propose a new representation setting for hedonic games, where each agent partitions the set of other agents into friends, enemies, and neutral agents, with friends and enemies being ranked. Under the assumption that preferences are monotonic (respectively, antimonotonic) with respect to the addition of friends (respectively, enemies), we propose a bipolar extension of the responsive extension principle, and use this principle to derive the (partial) preferences of agents over coalitions. Then, for a number of solution concepts, we characterize partitions that necessarily or possibly satisfy them, and we study the related problems in terms of their complexity.



我々は快楽ゲームのための新しい表現設定を提案します。この設定では、各エージェントは他のエージェントの集合を友人、敵、中立エージェントに分割し、友人と敵は順位付けされます。友人（敵）の追加に関して選好はそれぞれ単調（反単調）であるという仮定の下、応答的拡張原理の双極拡張を提案し、この原理を用いて提携におけるエージェントの（部分的な）選好を導出します。次に、いくつかの解概念について、それらを必然的に、あるいはおそらく満たす分割を特徴付け、関連する問題をその複雑さの観点から研究します。

Compositionality Decomposed: How do Neural Networks Generalise?

Compositionality Decomposed: How do Neural Networks Generalise? / 構成性の分解：ニューラルネットワークはどのように一般化するのか？

Despite a multitude of empirical studies, little consensus exists on whether neural networks are able to generalise compositionally, a controversy that, in part, stems from a lack of agreement about what it means for a neural model to be compositional. As a response to this controversy, we present a set of tests that provide a bridge between, on the one hand, the vast amount of linguistic and philosophical theory about compositionality of language and, on the other, the successful neural models of language. We collect different interpretations of compositionality and translate them into five theoretically grounded tests for models that are formulated on a task-independent level. In particular, we provide tests to investigate (i) if models systematically recombine known parts and rules (ii) if models can extend their predictions beyond the length they have seen in the training data (iii) if models’ composition operations are local or global (iv) if models’ predictions are robust to synonym substitutions and (v) if models favour rules or exceptions during training. To demonstrate the usefulness of this evaluation paradigm, we instantiate these five tests on a highly compositional data set which we dub PCFG SET and apply the resulting tests to three popular sequence-to-sequence models: a recurrent, a convolution-based and a transformer model. We provide an in-depth analysis of the results, which uncover the strengths and weaknesses of these three architectures and point to potential areas of improvement.



多くの実証研究があるにもかかわらず、ニューラルネットワークが構成的に一般化できるかどうかについてはほとんどコンセンサスがなく、この論争は部分的には、ニューラルモデルが構成的であるという意味についての合意の欠如に起因しています。この論争への回答として、我々は、言語の構成性に関する膨大な言語学および哲学的理論と、他方で成功した言語のニューラルモデルとの橋渡しとなる一連のテストを提示します。構成性のさまざまな解釈を収集し、それらをタスク非依存レベルで定式化されたモデルに対する理論的根拠のある5つのテストに変換します。特に、(i)モデルが既知の部分と規則を体系的に再結合するかどうか、(ii)モデルがトレーニングデータで見た長さを超えて予測を拡張できるかどうか、(iii)モデルの構成操作がローカルかグローバルか、(iv)モデルの予測が同義語の置換に対してロバストかどうか、(v)モデルがトレーニング中に規則または例外を優先するかどうかを調べるためのテストを提供します。この評価パラダイムの有用性を示すため、PCFG SETと名付けた高度に構成的なデータセットにこれら5つのテストを実装し、得ら​​れたテストを3つの一般的なシーケンスツーシーケンスモデル（リカレントモデル、畳み込みベースモデル、トランスフォーマーモデル）に適用します。その結果を詳細に分析し、これら3つのアーキテクチャの長所と短所を明らかにし、改善の余地のある領域を指摘します。

Incomplete Preferences in Single-Peaked Electorates

Incomplete Preferences in Single-Peaked Electorates / 単峰性選挙区における不完全な選好

Incomplete preferences are likely to arise in real-world preference aggregation scenarios. This paper deals with determining whether an incomplete preference profile is single-peaked. This is valuable information since many intractable voting problems become tractable given singlepeaked preferences. We prove that the problem of recognizing single-peakedness is NP-complete for incomplete profiles consisting of partial orders. Despite this intractability result, we find several polynomial-time algorithms for reasonably restricted settings. In particular, we give polynomial-time recognition algorithms for weak orders, which can be viewed as preferences with indifference.



不完全な選好は、現実世界の選好集約シナリオにおいて発生する可能性があります。本論文では、不完全な選好プロファイルが単峰性であるかどうかを判定する手法を扱います。単峰性の選好が与えられると、多くの扱いにくい投票問題が扱いやすくなるため、これは貴重な情報です。単峰性を認識する問題は、部分順序からなる不完全なプロファイルに対してNP完全であることを証明します。この扱いにくい結果にもかかわらず、ある程度制限された設定に対して、いくつかの多項式時間アルゴリズムが見つかりました。特に、無差別選好と見なせる弱い順序に対する多項式時間認識アルゴリズムを示します。

The 2^k Neighborhoods for Grid Path Planning

The 2^k Neighborhoods for Grid Path Planning / グリッドパス計画のための2^k近傍

Grid path planning is an important problem in AI. Its understanding has been key for the development of autonomous navigation systems. An interesting and rather surprising fact about the vast literature on this problem is that only a few neighborhoods have been used when evaluating these algorithms. Indeed, only the 4- and 8-neighborhoods are usually considered, and rarely the 16-neighborhood. This paper describes three contributions that enable the construction of effective grid path planners for extended 2k-neighborhoods; that is, neighborhoods that admit 2k neighbors per state, where k is a parameter. First, we provide a simple recursive definition of the 2k-neighborhood in terms of the 2k-1-neighborhood. Second, we derive distance functions, for any k ≥ 2, which allow us to propose admissible heuristics that are perfect for obstacle-free grids, which generalize the well-known Manhattan and Octile distances. Third, we define the notion of canonical path for the 2k-neighborhood; this allows us to incorporate our neighborhoods into two versions of A*, namely Canonical A* and Jump Point Search (JPS), whose performance, we show, scales well when increasing k. Our empirical evaluation shows that, when increasing k, the cost of the solution found improves substantially.  Used with the 2k-neighborhood, Canonical A* and JPS, in many configurations, are also superior to the any-angle path planner Theta* both in terms of solution quality and runtime. Our planner is competitive with one implementation of the any-angle path planner, ANYA in some configurations. Our main practical conclusion is that standard, well-understood grid path planning technology may provide an effective approach to any-angle grid path planning.



グリッドパスプランニングはAIにおける重要な問題です。その理解は、自律航法システムの開発の鍵となっています。この問題に関する膨大な文献の中で興味深く、かつむしろ驚くべき事実は、これらのアルゴリズムの評価に使用された近傍がごくわずかであるということです。実際、通常は4近傍と8近傍のみが考慮され、16近傍が考慮されることはほとんどありません。この論文では、拡張2k近傍、つまり状態ごとに2k個の近傍を許容する近傍(kはパラメーター)に対する効果的なグリッド パス プランナーの構築を可能にする3つの貢献について説明します。まず、2k-1近傍の観点から2k近傍の単純な再帰定義を提供します。次に、任意のk≥2について距離関数を導出します。これにより、障害物のないグリッドに最適な許容ヒューリスティックスを提案することができ、よく知られているマンハッタン距離とオクタイル距離を一般化できます。3つ目に、2k近傍の標準パスの概念を定義します。これにより、近傍を2つのバージョンのA*、つまり標準A*とジャンプ ポイント検索(JPS)に組み込むことができ、kの増加に応じてパフォーマンスが適切にスケーリングされることがわかります。経験的評価では、kが増加すると、見つかったソリューションのコストが大幅に改善されることが示されています。2k近傍法を用いたCanonical A*とJPSは、多くの構成において、解の品質と実行時間の両面で任意角度パスプランナーTheta*よりも優れています。私たちのプランナーは、いくつかの構成において、任意角度パスプランナーの実装の一つであるANYAと競合可能です。私たちの主な実用的な結論は、標準的で十分に理解されているグリッドパスプランニング技術が、任意角度グリッドパスプランニングへの効果的なアプローチとなる可能性があるということです。

HTN Planning as Heuristic Progression Search

HTN Planning as Heuristic Progression Search / ヒューリスティック進行探索としてのHTN計画

The majority of search-based HTN planning systems can be divided into those searching a space of partial plans (a plan space) and those performing progression search, i.e., that build the solution in a forward manner. So far, all HTN planners that guide the search by using heuristic functions are based on plan space search. Those systems represent the set of search nodes more effectively by maintaining a partial ordering between tasks, but they have only limited information about the current state during search. In this article, we propose the use of progression search as basis for heuristic HTN planning systems. Such systems can calculate their heuristics incorporating the current state, because it is tracked during search. Our contribution is the following: We introduce two novel progression algorithms that avoid unnecessary branching when the problem at hand is partially ordered and show that both are sound and complete. We show that defining systematicity is problematic for search in HTN planning, propose a definition, and show that it is fulfilled by one of our algorithms. Then, we introduce a method to apply arbitrary classical planning heuristics to guide the search in HTN planning. It relaxes the HTN planning model to a classical model that is only used for calculating heuristics. It is updated during search and used to create heuristic values that are used to guide the HTN search. We show that it can be used to create HTN heuristics with interesting theoretical properties like safety, goal-awareness, and admissibility. Our empirical evaluation shows that the resulting system outperforms the state of the art in search-based HTN planning.



探索ベースのHTNプランニングシステムの大部分は、部分プランの空間（プラン空間）を探索するものと、漸進探索（つまり、解を前向きに構築する）を行うものに分けられます。これまで、ヒューリスティック関数を用いて探索を誘導するHTNプランナーはすべて、プラン空間探索に基づいています。これらのシステムは、タスク間の部分順序を維持することで探索ノードの集合をより効果的に表現しますが、探索中の現在の状態に関する情報は限られています。本稿では、漸進探索をヒューリスティックHTNプランニングシステムの基盤として用いることを提案します。このようなシステムは、探索中に現在の状態を追跡するため、現在の状態を考慮に入れてヒューリスティックを計算することができます。本稿の貢献は以下のとおりです。問題が部分順序である場合に不要な分岐を回避する2つの新しい漸進アルゴリズムを導入し、どちらも健全かつ完全であることを示します。HTNプランニングにおける探索において、体系性の定義が困難であることを示し、定義を提案し、本稿のアルゴリズムの1つが体系性を満たすことを示します。次に、HTNプランニングにおける探索をガイドするために、任意の古典的なプランニング ヒューリスティックを適用する手法を紹介します。この手法は、HTNプランニング モデルを、ヒューリスティックの計算にのみ使用される古典的なモデルに緩和します。このモデルは探索中に更新され、HTN探索をガイドするヒューリスティック値を作成するために使用されます。この手法を使用して、安全性、目標認識、許容性などの興味深い理論的特性を持つHTNヒューリスティックを作成できることを示します。実証的評価では、結果として得られるシステムが、探索ベースのHTNプランニングにおける最先端のシステムよりも優れていることが示されています。

Learning the Language of Software Errors

Learning the Language of Software Errors / ソフトウェアエラーの言語学習

We propose to use algorithms for learning deterministic finite automata (DFA), such as Angluin’s L* algorithm, for learning a DFA that describes the possible scenarios under which a given program error occurs. The alphabet of this automaton is given by the user (for instance, a subset of the function call sites or branches), and hence the automaton describes a user-defined abstraction of those scenarios. More generally, the same technique can be used for visualising the behavior of a program or parts thereof. It can also be used for visually comparing different versions of a program (by presenting an automaton for the behavior in the symmetric difference between them), and for assisting in merging several development branches. We present experiments that demonstrate the power of an abstract visual representation of errors and of program segments, accessible via the project’s web page. In addition, our experiments in this paper demonstrate that such automata can be learned efficiently over real-world programs. We also present lazy learning, which is a method for reducing the number of membership queries while using L*, and demonstrate its effectiveness on standard benchmarks.



特定のプログラム エラーが発生する可能性のあるシナリオを記述するDFAを学習するために、AngluinのL*アルゴリズムなどの決定性有限オートマトン(DFA)を学習するためのアルゴリズムを使用することを提案します。このオートマトンにアルファベット(関数呼び出しサイトまたは分岐のサブセットなど)はユーザーによって指定されるため、オートマトンではこれらのシナリオのユーザー定義の抽象化が記述されます。より一般的には、同じ手法を用いてプログラム全体またはその一部の動作を視覚化することができます。また、異なるバージョンのプログラムを視覚的に比較（それらの間の対称的な差異における動作のオートマトンを提示することにより）したり、複数の開発ブランチのマージを支援したりするためにも使用できます。本稿では、プロジェクトのウェブページからアクセスできる、エラーとプログラムセグメントの抽象的な視覚表現の威力を示す実験を紹介します。さらに、本稿の実験では、このようなオートマトンが実際のプログラムで効率的に学習できることを実証しています。また、L*を使用しながらメンバーシップクエリの数を減らす手法である遅延学習も紹介し、標準的なベンチマークでその有効性を示します。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 67 (2020)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧