Human-Centered ASP Applications: Representation & Reasoning

Instead of finding continuous plans for the agents, it is possible to simplify this problem by relaxing it into a discrete problem.

One relaxation that can be done is considering the time as discrete time steps instead of continuous time, and the limit on the time as a limit on maximum or total number of time steps of the resulting plans.

Similarly, instead of considering the whole warehouse as a continuous space, we can represent it as a graph. We can divide the environment into smaller areas and represent each area as a vertex and add undirected edges between every two adjacent small area. Furthermore, we can choose these smaller areas in such a way that each robot can fit inside a vertex and each vertex can contain at most one robot. In this way, we do not need to consider the size or shape of the robots while computing our plans.

With these relaxations, we do not have to plan for every instant of time and we do not need to consider every point of the environment while planning. We will only consider at which vertex the robots are located at, for every time step. At each step, the robots can either stay at their current locations or move to an adjacent vertex. From the positions specified as the initial and goal configurations of the robots, we can identify at which vertex the robot starts at and at which vertex it should arrive at the end as well.

This representation of the environment and the the idea of having a solution for discrete time steps is also useful when we think about possible collisions. For the collisions between the robots, since only one robot can fit inside a vertex due to how we constructed our graph, we can say that no two robots can be at a vertex at the same time. Similarly, if we think about the edges of our graph, we can say that at most one robot can fit on an edge (due to how we set our vertices), and we can identify the collisions occurring on the edges when they are shared by two agents at the same time interval. Remember that with our simplification, we only need to compute which vertex the robot visits at each time step, so we would not have explicit information about the time at which an edge is visited by a robot. Thus we need to consider the vertices at the endpoints of the edges and at which step they are visited. Note that the robots are not allowed to wait on an edge with our simplification, so the endpoints of an edge would be visited in consecutive time steps.

This discretized problem is called Multi-Agent Path Finding (MAPF) problem [15]. It is a combinatorial search problem with different application areas, including automated warehouses [16].

First, let us precisely describe the input of the simplified MRP problem, according to our discussions above:

• $\mathrm{■}$

  a set $A=\{a_1,a_2,\mathrm{\dots },a_n\}$ of agents representing the robots,

• $\mathrm{■}$

  an undirected graph $G=(V,E)$ representing the environment,

• $\mathrm{■}$

  an integer $\tau$, denoting the upper bound on the time steps,

• $\mathrm{■}$

  a function $init:A\to V$ that maps agents to their initial locations (vertices),

• $\mathrm{■}$

  a function $goal:A\to V$ that maps agents to their goal locations,

• $\mathrm{■}$

  a set $O\subseteq V$, denoting the vertices blocked by obstacles.

Given these input, the aim is to find the collision-free plans of the robots (i.e., the mapping from time steps to vertices from initial vertex to goal vertex). Then the output consists of the following, for every agent $a_i\in A$, for some positive integer $u\le \tau$:

• $\mathrm{■}$

  a path $P_i=⟨v_{i,0},\mathrm{\dots },v_{i,l_i}⟩$ of finite length $l_i$ ($l_i\le u$) such that

  • –

    $v_{i,j}\in V\setminus O$ (i.e. no collisions with obstacles),

  • –

    for every $⟨v_{i,j},v_{i,j+1}⟩$ in $P$, there exists an edge $\{v_{i,j},v_{i,j+1}\}\in E$ (i.e. the path is connected)

  • –

    $v_{i,0}=init(a_i)$ (i.e. the path starts from the agent’s initial location),

  • –

    $v_{i,l_i}=goal(a_i)$ (i.e. the path ends at the agent’s goal location), and

• $\mathrm{■}$

  a traversal $f_i$ of the path $P_i$, where $f_i$ is a function that maps every integer $t$ ($0\le t\le u$) to a vertex in $P_i$ such that

  • –

    for every $t$, if $f_i(t)=v_{i,k}$ then $f_i(t+1)=v_{i,k}$ or $f_i(t+1)=v_{i,k+1}$, and

  • –

    for every other agent $a_j\in A$ with traversal $f_j$ of path $P_j$,

    • *

      for every $t$ where $0\le t\le u$, $f_i(t)\ne f_j(t)$ (i.e no two agents are at the same vertex at the same time), and

    • *

      for every $t$ where , if $f_i(t)=f_j(t+1)$, then $f_i(t+1)\ne f_j(t)$ (i.e no two agents can swap their locations).

Now that we have a mathematical model of MAPF problem, let us represent it formally in ASP.

Although our model of MAPF addresses the main problem of planning routes for multiple agents in a shared environment, solving MAPF may not be sufficient for addressing other challenges of a real-world automated warehouse.

For instance, since the robots in an automated warehouse are mobile robots, they are equipped with batteries. The battery levels of robots will decrease as they move around and therefore they may need charging. To address this, we can extend our mathematical model to take battery levels into account, as well as charging stations in the environment. Integrating battery levels and charging into our model and encoding would benefit the users of our methods, since they would not have to keep track of when the robots need charging.

Another challenge that is not addressed by MAPF occurs when we consider a warehouse where robots and humans work together in a shared environment. To ensure the safety of human workers, robots may need to move slower than usual in the specific parts of the warehouse. If we extend our model to consider different speeds for the robots, we can generate plans that would be more useful in this setting, by ensuring the safety of human workers.

As an example, consider the instance shown in Figure 2(a) in a small warehouse, viewed as a 3x4 grid. The warehouse contains a shelf unit that occupies two grid cells, denoted as obstacles shown by the black cells. As the robots move, their battery level decreases by 1 at each time step and they may need charging. For this purpose, the warehouse contains a charging station, denoted by the yellow cell located at Cell 10. If a robot is at a charging station, its battery level may quickly get to the maximum level or the robot can move forward without charging its battery. In the corridor denoted by red cells, the robots should move slowly, due to humans working nearby. Normally, it takes one time step for a robot to move from one grid cell to the other, but in this slow corridor it takes two time steps to move from one cell to the next. When the robot is located between two grid cells, we say that it is “in transit”. There are two robots, $A1$ and $A2$, in this warehouse and they are initially located in two corners, denoted by the colored circles. The robots aim to swap their places at the end. The stars denote the waypoint of the same colored robot and the robot must visit its waypoint to pick up items on its way to its goal location. An optimal solution for this instance is illustrated in Figure 2(b).

While working on Exercise 3, we need to keep in mind that the end-users may request further extensions, so elaboration tolerance is important for a general and flexible representation [2].

In addition to the extensions to the problem to address more challenges, the engineers who will execute the solutions computed by our methods may want to learn more about the solution that they want to execute in the warehouse.

For instance, the engineer may ask about whether some modifications on the executed plan would be feasible or not. A modification can include changing a location visited by an agent or changing when an agent waits at a location. Moreover, if we consider the extensions discussed above, the engineer may want to check if it is feasible not to charge a specific robot.

Providing only a yes/no answer about feasibility may not be very informative for the users. In addition to an answer about feasibility, we can provide explanations on why this modification is feasible or not.

Let $A$ be a finite set of agents. For every agent $x\in A$, let $A_x\subseteq A\backslash \{x\}$ be a set of agents that are acceptable to $x$ as roommates. We assume that $x$ prefers $y$ as a roommate compared to being single.

Each agent has a preference lists ${\prec }_x$, which is a partial order over $A_x$ where incomparability is transitive, that is, if a student cannot compare $x$ with $y$, and also cannot compare $y$ with $z$, then we treat it as though they also cannot compare $x$ with $z$. This avoids creating inconsistencies in the preference list. We denote by $y{\prec }_{x}z$ that $x$ prefers $y$ to $z$. An agent $x$ is indifferent between the agents $y$ and $z$, denoted by $y{\sim }_{x}z$, if $y{\nprec }_{x}z$ and $z{\nprec }_{x}y$.

An SRTI instance $(A,\prec )$ is then characterized by the set of agents and the collection $\prec$ of preference lists of all agents in $A$.

A matching for a given SRTI instance $(A,\prec )$ is a function $M:A\mapsto A$ such that, for all $\{x,y\}\subseteq A\times A$ where $x\in A_y$ and $y\in A_x$, $M(x)=y$ iff $M(y)=x$. If agent $x$ is mapped to itself, then we say that it is single.

A matching $M$ is blocked by a pair $\{x,y\}\subseteq A\times A$ ($x\ne y$) if

1. B1

   both agents $x$ and $y$ are acceptable to each other,

2. B2

   $x$ is single with respect to $M$, or $y{\prec }_{x}M(x)$, and

3. B3

   $y$ is single with respect to $M$, or $x{\prec }_{y}M(y)$.

A matching for SRTI is called stable if it is not blocked by any pair of agents.

An SRTI instance $I=(A,\prec )$ can be described by a set of facts in ASP, with atoms of the forms $\text{agent}(x)$ (“$x$ is an agent in $A$”) and $\text{prefer2}(x,y,z)$ (“agent $x$ prefers agent $y$ to agent $z$, i.e., $y{\prec }_{x}z$ ”).

We assume that, for every agent $x$, assigning a roommate to $x$ is preferred to not assigning anyone to $x$ (e.g., for the dormitories to accommodate more students). Therefore, as part of input, for every $y\in A_x$, we include facts of the form $\text{prefer2}(x,y,x)$.

A matching $M:A\mapsto A$ for an SRTI instance is characterized by atoms of the form $\text{room}(x,y)$ (“agents $x$ and $y$ are roommates”).

To represent SRTI problem in ASP, we also need to define some auxiliary concepts, like acceptability and blocking.

In real-world applications, when there is no stable matching to a given SRTI problem instance, we still need to find a “good enough” matching as the students should be assigned roommates. This observation has led to some reasonable relaxations of the problem, such as Almost SRTI. Here the goal is to minimize the number of blocking pairs, so a good enough matching is one with a small number of blocking pairs.

However, there are still challenges when we consider the cases in the real world. For instance, most of the freshmen students often do not know any peers and leave their preferences empty. If most of the preference lists are empty, Almost SRTI may not lead to a good enough solution.

On the other hand, note that in many universities and colleges,²²2Cleveland Clinic Student Housing application: https://my.clevelandclinic.org/-/scassets/files/org/professionals/student-housing/roommate-questionnaire-worksheet additional compatibility criteria, such as lifestyle habits or study environment preferences, are often collected through questionnaires. Can we utilize this additional information to find a “better” roommate matching, e.g., for such freshmen students? Let us try!

Suppose that the originally given SRTI instance $(A,\prec )$ does not have a stable matching but the Personalized-SRTI instance $(A,\prec ,P^{\prime })$ built on top of it by augmenting additional personal information does have a stable matching. In this case, usefulness evaluations need to answer the following question:

How good is a personalized stable matching, compared to unstable matchings for $(A,\prec )$?

Alternatively, suppose that both the originally given SRTI instance $(A,\prec )$ and the Personalized-SRTI instance $(A,\prec ,P^{\prime })$ have stable matchings. In this case, usefulness evaluations need to answer the following question:

How good are the personalized stable matchings of $(A,\prec ,P^{\prime })$, compared to the stable matchings of $(A,\prec )$?

To be able to answer such questions, usefulness evaluations require feedback from a diverse set of end-users, via surveys, polls and interviews. However, designing and conducting human-subject empirical analysis is quiet challenging.

For instance, in our earlier studies [4], to answer the two questions above about the usefulness of personalized-SRTI, we have designed follow-up surveys with one or two short questions about a few small SRTI instances. These instances are described by text and figures for easier understandability, and the questions require short answers without increasing the cognitive load of the participants. Figure 4 illustrates one of the survey questions.

We have conducted these surveys with more than 200 students at Sabanci University as diverse as possible, after briefly informing them about the purpose of the study and getting their approvals. During these interactions, it is important not to misguide the participants and to introduce any biases.

The survey results confirm that extending SRTI to include further knowledge about the agents indeed provides practical benefits in finding stable/better matchings [4].