Van Nguyen

KR Conference 2020 Conference Paper

Explainable Planning Using Answer Set Programming

• Van Nguyen
• Stylianos Loukas Vasileiou
• Tran Cao Son
• William Yeoh

In human-aware planning problems, the planning agent may need to explain its plan to a human user, especially when the plan appears infeasible or suboptimal for the user. A popular approach to do so is called model reconciliation, where the planning agent tries to reconcile the differences between its model and the model of the user such that its plan is also feasible and optimal to the user. This problem can be viewed as an optimization problem, where the goal is to find a subset-minimal explanation that one can use to modify the model of the user such that the plan of the agent is also feasible and optimal to the user. This paper presents an algorithm for solving such problems using answer set programming.

UAI Conference 2017 Conference Paper

Approximate Evidential Reasoning Using Local Conditioning and Conditional Belief Functions

• Van Nguyen

We propose a new message-passing belief propagation method that approximates belief updating on evidential networks with conditional belief functions. By means of local conditioning, the method is able to propagate beliefs on the original multiply-connected network structure using local computations, facilitating reasoning in a distributed and dynamic context. Further, by use of conditional belief functions in the form of partially defined plausibility and basic plausibility assignment functions, belief updating can be efficiently approximated using only partial information of the belief functions involved. Experiments show that the method produces results with high degree of accuracy whilst achieving a significant decrease in computational and space complexity (compared to exact methods).

IJCAI Conference 2017 Conference Paper

Generalized Target Assignment and Path Finding Using Answer Set Programming

• Van Nguyen
• Philipp Obermeier
• Tran Cao Son
• Torsten Schaub
• William Yeoh

In Multi-Agent Path Finding (MAPF), a team of agents needs to find collision-free paths from their starting locations to their respective targets. Combined Target Assignment and Path Finding (TAPF) extends MAPF by including the problem of assigning targets to agents as a precursor to the MAPF problem. A limitation of both models is their assumption that the number of agents and targets are equal, which is invalid in some applications such as autonomous warehouse systems. We address this limitation by generalizing TAPF to allow for (1)~unequal number of agents and tasks; (2)~tasks to have deadlines by which they must be completed; (3)~ordering of groups of tasks to be completed; and (4)~tasks that are composed of a sequence of checkpoints that must be visited in a specific order. Further, we model the problem using answer set programming (ASP) to show that customizing the desired variant of the problem is simple one only needs to choose the appropriate combination of ASP rules to enforce it. We also demonstrate experimentally that if problem specific information can be incorporated into the ASP encoding then ASP based method can be efficient and can scale up to solve practical applications.

SODA Conference 2005 Conference Paper

Analyzing and characterizing small-world graphs

• Van Nguyen
• Charles U. Martel