Search for: All records

Earlier epistemic planning systems for multi-agent domains generate plans that contain various types of actions such as ontic, sensing, or announcement actions. However, none of these systems consider untruthful announcements, i.e., none can generate plans that contain a lying or a misleading announcement. In this paper, we present a novel epistemic planner, called EFP3.0, for multi-agent domains with untruthful announcements. The planner is similar to the systems EFP or EFP2.0 in that it is a forward-search planner and can deal with unlimited nested beliefs and common knowledge by employing a Kripke based state representation and implementing an update model based transition function. Different from EFP, EFP3.0 employs a specification language that uses edge-conditioned update models for reasoning about effects of actions in multi-agent domains. We describe the basics of EFP3.0 and conduct experimental evaluations of the system against state-of-the-art epistemic planners. We discuss potential improvements that could be useful for scalability and efficiency of the system. 

Explainable artificial intelligence (XAI) aims at addressing complex problems by coupling solutions with reasons that justify the provided answer. In the context of Answer Set Programming (ASP) the user may be interested in linking the presence or absence of an atom in an answer set to the logic rules involved in the inference of the atom. Such explanations can be given in terms of directed acyclic graphs (DAGs). This article reports on the advancements in the development of the XAI system xASP by revising the main foundational notions and by introducing new ASP encodings to compute minimal assumption sets, explanation sequences, and explanation DAGs. 

The Multi-Agent Path Finding (MAPF) is a problem of finding a plan for agents to reach their desired locations without colliding. Distributed Multi-Agent Path Finder (DMAPF) solves the MAPF problem by decomposing a given MAPF problem instance into smaller subproblems and solve them in parallel. DMAPF works in rounds. Between two consecutive rounds, agents may migrate between two adjacent subproblems following their abstract plans, which are pre-computed, until all of them reach the areas that contain their desired locations. Previous works on DMAPF compute an abstract plan for each agent without the knowledge of other agents’ abstract plans, resulting in high congestion in some areas, especially those that act as corridors. The congestion negatively impacts the runtime of DMAPF and prevents it from being able to solve dense MAPF problems. In this paper, we (i) investigate the use of Uniform-Cost Search to mitigate the congestion. Additionally, we explore the use of several other techniques including (ii) using timeout estimation to preemptively stop solving and relax a subproblem when it is likely to get stuck; (iii) allowing a solving process to manage multiple subproblems – aimed to increase concurrency; and (iv) integrating with MAPF solvers from the Conflict-Based Search family. Experimental results show that our new system is several times faster than the previous ones; can solve larger and denser problems that were unsolvable before; and has better runtime than PBS and EECBS, which are state-of-the-art centralized suboptimal MAPF solvers, in problems with a large number of agents. 

A warehouse delivery problem consists of a set of robots that undertake delivery jobs within a warehouse. Items are moved around the warehouse in response to events. A solution to a warehouse delivery problem is a collision-free schedule of robot movements and actions that ensures that all delivery jobs are completed and each robot is returned to its docking station. While the warehouse delivery problem is related to existing research, such as the study of multi-agent path finding (MAPF), the specific industrial requirements necessitated a novel approach that diverges from these other approaches. For example, our problem description was more suited to formalizing the warehouse in terms of a weighted directed graph rather than the more common grid-based formalization. We formalize and encode the warehouse delivery problem in Answer Set Programming (ASP) extended with difference constraints. We systematically develop and study different encoding variants, with a view to computing good quality solutions in near real-time. In particular, application specific criteria are contrasted against the traditional notion of makespan minimization as a measure of solution quality. The encoding is tested against both crafted and industry data and experiments run using the Hybrid ASP solver clingo[dl]. 

Inspired by the recent problems in supply chains, we propose an approach to declarative modeling of contracts between agents that will eventually support reasoning about resilience of and about ways to improve supply chains. Specifically, we present a high-level language for specifying and reasoning about contracts over action domains of agents. We assume that the behavior of the agents can be formally expressed through action theories and view a contract as a collection of constraints. Each constraint specifies the responsibility of an agent to achieve a certain result by a deadline. Each agent also has a mapping between constraints and the agent’s concerns, i.e. issues that the agent is concerned about, which are modeled in accordance with the CPS Framework proposed by the National Institute of Standards and Technology. We discuss how common questions related to the fulfillment of a contract or the concerns of the agents can be answered and computed via Answer Set Programming. 

Abstract Answer Set Planning refers to the use of Answer Set Programming (ASP) to compute plans , that is, solutions to planning problems, that transform a given state of the world to another state. The development of efficient and scalable answer set solvers has provided a significant boost to the development of ASP-based planning systems. This paper surveys the progress made during the last two and a half decades in the area of answer set planning, from its foundations to its use in challenging planning domains. The survey explores the advantages and disadvantages of answer set planning. It also discusses typical applications of answer set planning and presents a set of challenges for future research.