Temporal Reasoning for a Collaborative Planning Agent in a Dynamic Environment

We present a temporal reasoning mechanism for an individual agent situated in a dynamic environment such as the web and collaborating with other agents while interleaving planning and acting. Building a collaborative agent that can flexibly achieve its goals in changing environments requires a blending of real-time computing and AI technologies. Therefore, our mechanism consists of an Artificial Intelligence (AI) planning subsystem and a Real-Time (RT) scheduling subsystem. The AI planning subsystem is based on a model for collaborative planning. The AI planning subsystem generates a partial order plan dynamically. During the planning it sends the RT scheduling subsystem basic actions and time constraints. The RT scheduling subsystem receives the dynamic basic actions set with associated temporal constraints and inserts these actions into the agent's schedule of activities in such a way that the resulting schedule is feasible and satisfies the temporal constraints. Our mechanism allows the agent to construct its individual schedule independently. The mechanism handles various types of temporal constraints arising from individual activities and its collaborators. In contrast to other works on scheduling in planning systems which are either not appropriate for uncertain and dynamic environments or cannot be expanded for use in multi-agent systems, our mechanism enables the individual agent to determine the time of its activities in uncertain situations and to easily integrate its activities with the activities of other agents. We have proved that under certain conditions temporal reasoning mechanism of the AI planning subsystem is sound and complete. We show the results of several experiments on the system. The results demonstrate that interleave planning and acting in our environment is crucial.     

Generation and Selection of Abductive Explanations for Non-Omniscient Agents

Among the non-monotonic reasoning processes, abduction is one of the most important. Usually described as the process of looking for explanations, it has been recognized as one of the most commonly used in our daily activities. Still, the traditional definitions of an abductive problem and an abductive solution mention only theories and formulas, leaving agency out of the picture. Our work proposes a study of abductive reasoning from an epistemic and dynamic perspective. In the first part we explore syntactic definitions of both an abductive problem in terms of an agent’s information and an abductive solution in terms of the actions that modify the agent’s information. We look at diverse kinds of agents, including not only omniscient ones but also those whose information is not closed under logical consequence and those whose reasoning abilities are not complete. In the second part, we look at an existing logical framework whose semantic model allows us to interpret the previously stated formulas, and we define two actions that represent forms of abductive reasoning.     

A Logic Based Asynchronous Multi-Agent System

We present a logic programming based asynchronous multi-agent system in which agents can communicate with one another; update themselves and each other; abduce hypotheses to explain observations, and use them to generate actions. The knowledge base of the agents is comprised of generalized logic programs, integrity constraints, active rules, and of abducibles. We characterize the interaction among agents via an asynchronous transition rule system, and provide a stable models based semantics. An example is developed to illustrate how our approach works.     

基于双向推理的主体框架

文章提出了一个基于双向推理的主体框架FBRA,它是一个混合型的主体框架,主体既是反应的又是慎思的。它的推理内核是正向推理和反向推理相结合。正向推理用于对环境的反应,包括对其他主体的反应。反向推理基于溯因推理,用于信念修正、规划、多主体协调和多主体通信等。     

Merging deductive and inductive reasoning for processing textual descriptions of inter-human conflicts

We report on a novel approach to modeling a dynamic domain with limited knowledge. A domain may include participating agents where we are uncertain about motivations and decision-making principles of some of these agents. Our reasoning setting for such domains includes deductive, inductive, and abductive components. The deductive component is based on situation calculus and describes the behavior of agents with complete information. The machine learning-based inductive and abductive components involve the previous experience with the agents, whose actions are uncertain to the system. Suggested reasoning machinery is applied to the problem of processing customer complaints in the form of textual messages that contain a multiagent conflict. The task is to predict the future actions of an opponent agent to determine the required course of action to resolve a multiagent conflict. This study demonstrates that the hybrid reasoning approach outperforms both stand-alone deductive and inductive components. Suggested methodology reflects the general situation of reasoning in dynamic domains in the conditions of uncertainty, merging analytical (rule-based) and analogy-based reasoning.     

基于动态描述逻辑的多主体协作模型

基于动态描述逻辑的主体模型和协作过程就是既考虑了智能主体的知识表示与推理问题,又紧密地结合主体的设计与编程问题,把表示与推理应用到主体的具体设计中．它充分利用了动态描述逻辑的统一的形式化框架,同时从静态的知识表示与推理和动态的运行与变化两个方面来刻画主体的心智状态和协作过程,探讨了主体信念、行为能力、目标和规划等心智要素的表示、推理与修改以及联合目标的形成、多目标的规划问题．多主体协作模型将理论和实践有机地结合起来,能够充分体现智能主体的本质特征与运行机制,为多主体系统的设计与编程奠定了很好的基础．     

基于描述逻辑的主体服务匹配

多主体系统中的服务匹配是智能主体和多主体系统等领域中的重要研究课题．描述逻辑是知识表示和推理的形式化工具，它提供了可判定的和可靠的推理服务．该文利用描述逻辑有效的推理功能，特别是它对概念包含关系的有效判断，把它与多主体系统的服务推理结合起来．充分利用描述逻辑具有清晰模型一理论语义和有效的概念分层推理服务等功能，该文提出了基于描述逻辑的主体服务匹配算法，详细研究了如何利用描述逻辑的理论和推理机制来实现自动的服务分层及服务匹配．并提出了五种服务匹配算法．这些方法都是基于语义的服务匹配，利用服务分层机制实现了有效和高效的多主体系统中的服务匹配，克服了基于语义距离进行服务匹配的不足．     

Motion feasibility of multi-agent formations

Formations of multi-agent systems, such as mobile robots, satellites and aircraft, require individual agents to satisfy their kinematic equations while constantly maintaining interagent constraints. In this paper, we develop a systematic framework for studying formation motion feasibility of multi-agent systems. In particular, we consider formations wherein all the agents cooperate to enforce the formation. We determine algebraic conditions that guarantee formation feasibility given the individual agent kinematics. Our framework also enables us to obtain lower dimensional control systems describing the group kinematics while maintaining all formation constraints.     

A multi-agent reinforcement learning approach to robot soccer

In this paper, a multi-agent reinforcement learning method based on action prediction of other agent is proposed. In a multi-agent system, action selection of the learning agent is unavoidably impacted by other agents’ actions. Therefore, joint-state and joint-action are involved in the multi-agent reinforcement learning system. A novel agent action prediction method based on the probabilistic neural network (PNN) is proposed. PNN is used to predict the actions of other agents. Furthermore, the sharing policy mechanism is used to exchange the learning policy of multiple agents, the aim of which is to speed up the learning. Finally, the application of presented method to robot soccer is studied. Through learning, robot players can master the mapping policy from the state information to the action space. Moreover, multiple robots coordination and cooperation are well realized.     

Reasoning about reasoning in a meta-level architecture

In this paper we discuss reasoning about reasoning in a multiple agent scenario. We consider agents that are perfect reasoners, loyal, and that can take advantage of both the knowledge and ignorance of other agents. The knowledge representation formalism we use is (full) first order predicate calculus, where different agents are represented by different theories, and reasoning about reasoning is realized via a meta-level representation of knowledge and reasoning. The framework we provide is pretty general: we illustrate it by showing a machine checked solution to the three wisemen puzzle. The agents' knowledge is organized into units: the agent's own knowledge about the world and its knowledge about other agents are units containing object-level knowledge; a unit containing meta-level knowledge embodies the reasoning about reasoning and realizes the link among units. In the paper we illustrate the meta-level architecture we propose for problem solving in a multi-agent scenario; we discuss our approach in relation to the modal one and we compare it with other meta-level architectures based on logic. Finally, we look at a class of applications that can be effectively modeled by exploiting the meta-level approach to reasoning about knowledge and reasoning.     

A sequential model of bargaining in logic programming

This paper proposes a sequential model of bargaining specifying reasoning processes of an agent behind bargaining procedures. We encode agents’ background knowledge, demands, and bargaining constraints in logic programs and represent bargaining outcomes in answer sets. We assume that in each bargaining situation, each agent has a set of goals to achieve, which are normally unachievable without an agreement among all the agents who are involved in the bargaining. Through an alternating-offers procedure, an agreement among bargaining agents may be reached by abductive reasoning. We show that the procedure converges to a Nash equilibrium if each agent makes rational offers/counteroffers in each round. In addition, the sequential model also has a number of desirable properties, such as mutual commitments, individual rationality, satisfactoriness, and honesty.     

Distributed partitioning algorithms for multi-agent networks with quadratic proximity metrics and sensing constraints

We consider a class of Voronoi-like partitioning problems, in which a multi-agent network seeks to subdivide a subset of an affine space into a finite number of cells in the presence of sensing constraints. The cell of this subdivision that is assigned to a particular agent consists exclusively of points that can be sensed by this agent and are closer to it than to any other agent that can also sense them. The proximity between an agent and an arbitrary point is measured in terms of a non-homogeneous quadratic (generalized) distance function, which does not, in general, enjoy the triangle inequality and the symmetry property. One of the consequences of this fact is that the structure of the sublevel sets of the utilized proximity metric does not conform with that of the sensing region of an agent. Due to this mismatch, it is possible that a point may be assigned to an agent which is different from its “nearest” agent simply because the nearest agent cannot sense this point, unless special care is taken. We propose a distributed partitioning algorithm that enables each agent to compute its own cell independently from the other agents when the only information available to it is the positions and the velocities of the agents that lie inside its sensing region. The algorithm is based on an iterative process that adjusts the size of the sensing region of each agent until the associated cell of the latter corresponds to the intersection of its sensing region with the cell that would have been assigned to it in the absence of sensing constraints. The correctness of the proposed distributed algorithm, which successfully handles the aforementioned issues, is studied in detail.     

一种基于约束传播的多主体规划算法

提出了一种基于约束传播的分布式多主体规划算法。主体之间的冲突检测与协调通过一种特殊的多主体协商来解决。在确定环境中该算法是可靠的。算法中主体之间交换的只是与冲突有关的动作、因果链和约束，具有通信量小、安全性高的优点。     

Multiagent reasoning with probability,time, and beliefs

Any agent interacting with the real world must be able to reason about uncertainty in the world, about the actions that may occur in the world (either due to the agent or those initiated by other agents), about the (probabilistic) beliefs of other agents, and how these (probabilistic) beliefs are changing over time. In this article, we develop a family of logics that a reasoning agent may use to perform successively more sophisticated types of reasoning in such environments. We also characterize different types of agents. Furthermore, we provide a logic that enables a systems designer (who may have populated an environment with a collection of such autonomous agents) to reason about the system of agents as a whole. © 1995 John Wiley & Sons, Inc.     

对称协调博弈问题的多智能体强化学习

针对多机器人协调问题,利用协调博弈中智能体策略相似性,提出智能体的高阶信念修正模型和学习方法PEL,使智能体站在对手角度进行换位推理,进而根据信念修正将客观观察行为和主观信念推理结合起来。证明了信念修正模型的推理置信度只在0和1两个值上调整即可协调成功。以多机器人避碰为实验背景进行仿真,表明算法比现有方法能够取得更好的协调性能。     

Multi-Agent Systems Specification and Certification: A Situation and State Calculus Approach

We address the topic of specifying multi-agent systems using the situation and state calculus (SSC). SSC has been proposed as an extension of the situation calculus to overcome some limitations of the usual notion of state. The envisaged multi-agent system specification framework allows the uniform treatment of both local and global properties, providing also techniques for reasoning about such specifications. When a certain intended property is not inferred from a specification, we cannot always just add to it the corresponding formula. Indeed, it is often the case that specification axioms are required to be formulae of a certain kind. The task of identifying the new axioms that should be added to the specification in order to ensure the intended property has an abductive nature. Herein, we develop abductive reasoning techniques to tackle this problem.     

A Constraint-Based Robotic Soccer Team

It is a challenging task for a team of multiple fast-moving robots to cooperate with each other and to compete with another team in a dynamic, real-time environment. For a robot team to play soccer successfully, various technologies have to be incorporated including robotic architecture, multi-agent collaboration and real-time reasoning. A robot is an integrated system, with a controller embedded in its plant. A robotic system is the coupling of a robot to its environment. Robotic systems are, in general, hybrid dynamic systems, consisting of continuous, discrete and event-driven components. Constraint Nets (CN) provide a semantic model for modeling hybrid dynamic systems. Controllers are embedded constraint solvers that solve constraints in real-time. A controller for our robot soccer team, UBC Dynamo98, has been modeled in CN, and implemented in Java, using the Java Beans architecture. A coach program using an evolutionary algorithm has also been designed and implemented to adjust the weights of the constraints and other parameters in the controller. The results demonstrate that the formal CN approach is a practical tool for designing and implementing controllers for robots in multi-agent real-time environments. They also demonstrate the effectiveness of applying the evolutionary algorithm to the CN-modeled controllers.     

Multi-Agent Constraint Systems with Preferences: Efficiency, Solution Quality, and Privacy Loss

In this paper, we consider multi-agent constraint systems with preferences, modeled as soft constraint systems in which variables and constraints are distributed among multiple autonomous agents. We assume that each agent can set some preferences over its local data, and we consider two different criteria for finding optimal global solutions: fuzzy and Pareto optimality. We propose a general graph-based framework to describe the problem to be solved in its generic form. As a case study, we consider a distributed meeting scheduling problem where each agent has a pre-existing schedule and the agents must decide on a common meeting that satisfies a given optimality condition. For this scenario we consider the topics of solution quality, search efficiency, and privacy loss, where the latter pertains to information about an agent's pre-existing meetings and available time-slots. We also develop and test strategies that trade efficiency for solution quality and strategies that minimize information exchange, including some that do not require inter-agent comparisons of utilities. Our experimental results demonstrate some of the relations among solution quality, efficiency, and privacy loss, and provide useful hints on how to reach a tradeoff among these three factors. In this work, we show how soft constraint formalisms can be used to incorporate preferences into multi-agent problem solving along with other facets of the problem, such as time and distance constraints. This work also shows that the notion of privacy loss can be made concrete so that it can be treated as a distinct, manipulable factor in the context of distributed decision making.