# Rapid Recovery from Robot Failures
in Multi-Robot Visibility-Based Pursuit-Evasion

Trevor Olsen, Nicholas M. Stiffler, and Jason M. O’Kane The authors are with
the Department of Computer Science and Engineering, University of South
Carolina, Columbia, SC 29208, USA<EMAIL_ADDRESS>{stifflen,
<EMAIL_ADDRESS>This material is based upon work supported by the National
Science Foundation under Grant Nos. 1659514 and 1849291.

###### Abstract

This paper addresses the visibility-based pursuit-evasion problem where a team
of pursuer robots operating in a two-dimensional polygonal space seek to
establish visibility of an arbitrarily fast evader. This is a computationally
challenging task for which the best known complete algorithm takes time doubly
exponential in the number of robots. However, recent advances that utilize
sampling-based methods have shown progress in generating feasible solutions.
An aspect of this problem that has yet to be explored concerns how to ensure
that the robots can recover from catastrophic failures which leave one or more
robots unexpectedly incapable of continuing to contribute to the pursuit of
the evader. To address this issue, we propose an algorithm that can rapidly
recover from catastrophic failures. When such failures occur, a replanning
occurs, leveraging both the information retained from the previous iteration
and the partial progress of the search completed before the failure to
generate a new motion strategy for the reduced team of pursuers. We describe
an implementation of this algorithm and provide quantitative results that show
that the proposed method is able to recover from robot failures more rapidly
than a baseline approach that plans from scratch.

##  I Introduction

For a number of important applications of mobile robots, including
environmental monitoring [15, 7, 34], disaster recovery [13], and surveillance
[2], the central problem is to plan motions for a team robots called
_pursuers_ to locate unpredictably moving agents called _evaders_. Though
progress has been made on several forms of this problem, a key limitation
within much of the existing work is an inability to adapt in cases of
unrecoverable failures of individual robots. Such failures are particularly
likely to occur in the very application domains for which these methods are
well-suited.

Figure 1 provides a simple illustration of this problem, in a context wherein
each pursuer is equipped with an omnidirectional sensor that can detect the
evaders within its line of sight. The objective is to move the pursuers along
paths that are guaranteed to locate the evaders, even if the evaders may move
arbitrarily quickly. An initial plan to search this environment using three
robots appears on the left of Figure 1. Now suppose the robot stationed at the
top left of the environment fails during the plan’s execution, as shown on the
right of Figure 1. In this case, any evader hiding in the center of the
environment at that time can now escape to the top left corner without being
detected. Thus, the initial plan is no longer guaranteed to locate the evader.

Figure 1: [left] An initial joint plan for 3 robots to search a simple
environment for an evader. Two robots on the left remain stationary and
monitor that side of the environment while a third moves to search the right.
[right] The robot in the top left corner fails unexpectedly. As a result, the
initial plan is no longer correct, because it cannot locate an evader that
moves into the top left corner of the environment.

Figure 2: [left] The robots from Figure 1 replan, using the proposed
algorithm, to form a correct plan for the remaining 2 robots. [right] The plan
completes successfully.

In response to this limitation, this paper proposes a new approach for this
form of visibility-based pursuit-evasion problem, suitable for contexts in
which failures of robots are likely. Because generating pursuit plans for this
domain is computationally challenging [29], we introduce a method for
replanning in cases of robot failure that leverages information derived from
the previous plan to accelerate the construction of new plans for the
unexpectedly-smaller teams. Figure 2 shows an example of recovery from the
failure depicted in Figure 1.

The central idea is to adapt known methods for solving these problems in the
failure-free case, which are based on a roadmap-like data structure called the
sample-generated pursuit-evasion graph (SG-PEG) [30]. For planning the motions
of $n$ robots in this pursuit-evasion problem, the SG-PEG graph represents the
connectivity of the joint configurations space with vertices that represent
joint configurations and edges that represent collision free movements, much
like a traditional probabilistic roadmap. In addition, each vertex is labeled
with information that encodes which hidden portions of the environment can be
cleared of unseen evaders along some walk in the graph ending at that vertex.
The new replanning approach modifies this data structure when a robot fails to
reflect the removal of that robot from the search. The remaining graph then
provides a valuable starting point for the process of planning to solve the
problem with the remaining $n-1$ robots. The algorithm then expands this graph
by adding additional vertices, attempting to recover the contributions made by
the failed robot.

This work is, to the authors’ best knowledge, the first to address the problem
of recovery from pursuer failures for this form of pursuit-evasion problem. In
the remainder of the paper, we review some related work (Section II), formally
define the problem (Section III). Then we describe and evaluate the algorithm
(Sections IV and V respectively) before concluding with discussion and a
preview of future work (Section VI).

##  II Related work

The visibility-based pursuit-evasion problem posed in this paper can be
thought of as a specialization of the broader problem of search and target
tracking. The common theme across this work is the pursuit of an agent (or
agents) by one (or more) pursuers to either establish or maintain visibility
of the target [27, 28, 39].

The literature on these problems can by understood by organizing according to
underlying models, including differential game theory, graph variants, and
geometric variants. Though this work considers the geometric formulation, we
present a brief synopsis of the contributions in the domains of differential
game theory and graph theory.

The seminal work of Isaacs [14] and Ho et. al. [12] was the first to adapt the
pursuit-evasion problem to a dynamic game-theoretic framework. This remains an
active research area [6, 18, 25, 36]. Recent results include continued
progress by utilizing techniques such as reinforcement learning [37] and the
exploitation of rich representations such as Voronoi partitions to aid in the
search [20, 38].

A different formulation in which the domain is modeled as a discrete graph was
initially proposed by Parsons [23] and is referred to as the edge-searching
problem. Petrov later independently rediscovered some of Parsons’ results in
the context of differential game theory [24]. Golovach later showed that both
problems considered an equivalent discrete game on graphs [9]. A number of
survey papers [1, 3, 5] provide overviews of the many problem variants that
can be realized within the graph model, such as specifying the rules of
movement for the pursuers and for the evaders [26], the kind of graph [17],
etc.

This paper specifically focuses on a variant of the problem where the pursuers
and evaders operate in a geometric environment [11, 22, 33]. There are a
number of results for the single pursuer variant of the problem that range
from providing theoretical properties such as completeness [11] and optimality
[31], to more restricted scenarios where there are limits on the actuation and
sensing capabilities of the pursuers [4, 19, 32, 35]. Due to the broad range
of practical applications, the multi-pursuer variant of the problem has drawn
continued interest [8, 10, 16], [30] in recent years. The multi-pursuer
scenario poses additional challenges owing to the problem complexity [29]. A
common thread through much of the existing work is an assumption that the
pursuer(s) can reliably execute the trajectories generated for them by the
planner. This work seeks to address this limitation.

##  III Problem statement

We first define the basic problem in the absence of pursuer failures (Section
III-A) and describe how to cast that problem in terms of a discrete
representation of which areas of the environment are ‘clear’ or ‘contaminated’
(Section III-B), before introducing the possibility of pursuer failures
(Section III-C).

###  III-A Environment, pursuers, and evaders

The _environment_ $F$ is a closed, bounded, and connected polygonal region in
$\mathbb{R}^{2}$. A team of $n$ _pursuers_ , who can travel throughout the
environment at bounded speed, are equipped with omnidirectional sensors whose
range is only bounded by line of sight within the environment. That is, a
pursuer at point $q\in F$ can detect anything within its _visibility polygon_
$V(q)=\\{r\in F\mid\overline{qr}\subset F\\}$. We denote the location of the
$i^{\text{th}}$ pursuer as a function of the time $t$ by the continuous
function $f_{i}(t):[0,T]\rightarrow F$, in which $T$ is some termination time
which the pursuers may choose. The $n$-robot _joint pursuer configuration_
(JPC) at time $t$ is the vector $\langle
f_{1}(t),f_{2}(t),\ldots,f_{n}(t)\rangle\in F^{n}$.

A single _evader_ seeks to avoid detection by the pursuers by moving
continuously within the environment, without any bound on its speed. We denote
its location, as a function of time, by the continuous function
$e(t):[0,\infty)\rightarrow F$, unknown to the pursuers. Observe that, because
we plan for the worst case, any strategy for the pursuers that guarantees
detection of a single evader can also guarantee detection for each of
potentially many evaders.

The pursuers’ objective is to establish visibility with the evader. Thus, for
a given environment $F$, the goal is to choose the termination time $T$ and
the functions $f_{1},f_{2},\ldots,f_{n}$ to ensure that for any evader
trajectory $e$, there exists a time $t_{0}\in[0,T]$, such that
$e(t_{0})\in\bigcup_{i\leq n}V(f_{i}(t_{0}))$. Figure 3 illustrates the
notation.

$f_{1}(0)$$f_{1}(t)$$f_{1}(T)$$f_{2}(0)$$f_{2}(t)$$f_{2}(T)$$e(0)$$e(t)$$e(T)$

Figure 3: Two pursuers execute a search. Note that at time $t$, the pursuer on
path $f_{2}$ is capable of detecting the evader $e$.

###  III-B Shadows

The primary difficulty in this type of visibility-based pursuit-evasion
concerns reasoning about the regions of the environment that are not currently
visible to the pursuers at the present time. To resolve that difficulty,
Guibas, Latombe, LaValle, Lin, and Motwani [11] introduced a reformulation of
the problem, based upon tracking which, if any, of the regions of the
environment not currently perceptible by the pursuers might contain an as-yet-
undetected evader.

To formalize this idea, define the _shadow region_ ,
$S(t)=F\setminus\bigcup_{i\leq n}V(f_{i}(t))$ as the portion of the
environment unseen by any pursuer at time $t$. The maximal connected
components of $S(t)$ are called _shadows_. The terms _cleared_ and
_contaminated_ can be applied to a shadow to reflect the relative _status_ of
the shadow at that point in the pursuers’ search. A cleared shadow is an
unseen area of the environment that, based upon the pursuers’ motions up to
the current time $t$, is guaranteed to not contain an unseen evader. Any
shadow that is not cleared is called contaminated.

To compactly describe the status for all of the shadows, we utilize a _shadow
label_ , which is a binary string comprised of one bit for each shadow, in
which the $i^{\text{th}}$ bit is $1$ if the $i^{\text{th}}$ shadow (in an
arbitrary but fixed ordering) is contaminated, and $0$ otherwise.

Though shadows change continuously as the pursuers move within $F$, the
cardinality of the shadows and their labels can change only when a shadow
event occurs, i.e. a shadow appears, disappears, splits, or multiple shadows
merge into a single shadow.

  * •

_Appear_ : A shadow appears when the pursuers move in such a way that makes a
previously observed part of the environment no longer visible. In this case,
the new shadow is assigned a cleared status.

  * •

_Disappear_ : If a pursuer gains vision of a shadow, we say the shadow
disappears. Here, the shadow bit is deleted.

  * •

_Split_ : If a pursuers’ vision disconnects a shadow, we say that the shadow
has split. Each new component is given the label of the original pre-split
shadow.

  * •

_Merge_ : If two or more shadows become a single connected component, we say
the shadows have merged. The newly merged shadow takes on the cleared status
if and only if each merging component was cleared prior to the merge.
Otherwise, the merged shadow is considered to be contaminated.

((a)) The initial location of a single pursuer. Here, the shadow label is 1.

((b)) Movement of a pursuer that would cause one shadow to appear and another
to split. The result has one cleared and two contaminated shadows. In our
implementation, this scenario is assigned shadow label 110.

Figure 4: An example of shadow events and labels.

This formulation of the problem in terms of clear and contaminated shadows is
valuable because it enables a planner to reason over those shadows and labels,
rather than directly over the space of all possible evader paths. That is, the
overall visibility-based pursuit-evasion problem can be restated as a search
for pursuer motions that lead to a system state in which the binary string of
shadow labels contains all zeroes, indicating that every shadow is clear.

###  III-C Pursuer Failures

The basic problem described so far has been addressed in prior work in a
number of different ways. The new contribution in this paper is to consider
this problem in an online setting, in which the pursuer robots may fail during
the execution of a plan. Such failures are assumed to be both unpredictable
and permanent, but known to all of the pursuers when they occur.

More precisely, we consider the case in which the $n$ pursuers are executing
the paths $f_{i}:[0,T]\to F$ for $i\in\\{1,\ldots,n\\}$, with termination time
$T$. Suppose that at some time $0\leq{\invbreve{t}}<T$, the $k^{\rm th}$
pursuer fails. The _replanning problem_ addressed in this paper is to generate
new pursuer paths $f_{i}^{\prime}:[{\invbreve{t}},T^{\prime}]\to F$ for
$i\in\\{1,\ldots,n\\}\setminus\\{k\\}$. These revised paths must begin at the
pursuers’ locations at the time of failure, so that for each surviving
pursuer, we have $f_{i}^{\prime}({\invbreve{t}})=f_{i}({\invbreve{t}})$. The
revised paths end at a new termination time $T^{\prime}$.

Generalizing the objective from the original failureless model, we say that
the pursuers’ execution of the prefix of $f_{1},\ldots,f_{n}$ up to time
${\invbreve{t}}$, followed by $f_{1}^{\prime},\ldots,f_{n}^{\prime}$ from time
${\invbreve{t}}$ to $T^{\prime}$ is a _solution_ if, for any evader trajectory
$e$, either (i) there exists a time $t_{0}\in[0,{\invbreve{t}}]$, such that
$e(t_{0})\in\bigcup_{i\leq n}V(f_{i}(t_{0}))$, or (ii) there exists a time
$t_{0}\in[{\invbreve{t}},T^{\prime}]$, such that $e(t_{0})\in\bigcup_{i\leq
n;i\neq k}V(f_{i}^{\prime}(t_{0}))$. That is, we seek to guarantee that the
evader is seen by any of the robots at some time before or after the pursuer
failure, or by one of the non-failing robots at some time after the failure.
Similar but notationally tedious generalizations can be made for multiple
failures within a single execution.

Fortunately, we can also generalize the notions of shadow label updates to
account for the abrupt change in shadows that occur at time ${\invbreve{t}}$.
Specifically, a shadow extant immediately after a robot failure is
contaminated if and only if it intersects with a contaminated shadow from
immediately before the failure occurred. Notice, for example, in the right
portion of Figure 1, that the large shadow encompassing the center and upper
left portion of the environment is marked contaminated because it overlaps the
central shadow which was contaminated before the failure. In contrast, the
smaller shadow in the lower right has a clear label after the failure, because
the only pre-failure shadow with which it intersects (namely, itself) had a
clear label. This feature of the definition of success, which allows shadows
to remain clear even across a failure of one of the pursuers, is crucial
because it allows the pursuers the possibility of retaining some of their
progress (i.e. cleared shadows) toward completing the task, rather than
starting from scratch each time.

##  IV Algorithm Overview

This section provides a detailed description of our algorithm. Because no
efficient algorithm for solving even the failure-free case is known [29], we
take a sampling-based approach. The basic idea is to construct a roadmap
within the pursuers’ joint configuration space, using an existing data
structure called the sample-generated pursuit-evasion graph (SG-PEG), which a
subset of the present authors originally introduced for the failure-free case
[30]. We leverage this data structure in a new way by introducing new sampling
strategies designed to rapidly re-acquire a solution in cases where a pursuer
must be removed.

The core of the algorithm is a method called DropRobot which, given a solution
path for $k$ robots (for some $k$), uses an SG-PEG to attempt to rapidly
generate a solution for $k-1$ robots, using the original $k$-robot solution as
a guide. Our algorithm relies upon DropRobot both to generate an initial
solution for the full set of $n$ robots —by iteratively reducing from a
rapidly-generated trivial solution— and for replanning when a pursuer fails.

The remainder of this section presents details of the method. After a brief
review of the SG-PEG (Section IV-A), we describe the DropRobot method (Section
IV-B) and how that method is used to generate the initial solution (Section
IV-C1) and for replanning (Section IV-C2).

###  IV-A SG-PEG

The SG-PEG is a data structure the represents a roadmap of valid joint paths
for a team of pursuers in a known environment $F$, augmented with information
about the shadow labels that can be achieved by executing those paths. We
present here a concise overview; additional detail may be found in the
original paper [30].

An SG-PEG is a directed graph $G=(V_{G},E_{G})$, in which one vertex $v_{0}$
is designated as the _root vertex_. Each SG-PEG is constructed for a specific
number $n$ of pursuers. Each vertex $v\in V_{G}$ corresponds to a specific JPC
$\langle p_{1},\ldots,p_{n}\rangle\in F^{n}$. Each directed edge $e\in E_{G}$
connects two vertices $v,u\in V_{G}$ for which it is possible for every
pursuer to make a collision-free straight line motion between the
representative configurations. That is, the existence of an edge from $v$ to
$u$ means that, for each $1\leq i\leq n$, $\overline{v_{i}u_{i}}\subset F$.

In addition to this graph structure, each vertex $v$ maintains a set of
reachable shadow labels. Specifically, a shadow label $\ell$ will be recorded
at a particular vertex $v$ as a reachable shadow label if there exists a walk
from $v_{0}$ to $v$ that results in the shadow marked clear within $\ell$
indeed being clear.

The primary operation that can be performed on a SG-PEG is
$\textsc{AddSample}(\langle p_{1},\ldots,p_{n}\rangle)$, which accepts a
collision-free JPC as input and performs the following steps:

  1. (i)

It inserts a new vertex $v$ at the given JPC.

  2. (ii)

For every existing vertex $u$ for which the segment $\overline{uv}$ is
collision free in $F^{n}$, it adds the edges $\overrightarrow{uv}$ and
$\overrightarrow{vu}$. The operation then computes a mapping that describes
how the shadows at vertex $u$ evolve as the pursuers move from the JPC at
vertex $u$ to the JPC at vertex $v$. (The inverse mapping is applied to
$\overrightarrow{vu}$).

  3. (iii)

Finally, the reachable shadow label information across the graph is updated by
propagating the reachable shadow labels, using the mappings attached to each
edge, recursively across the graph, to determine what new reachable shadow
labels, if any, arise due to the inclusion of the new sample $v$.

The SG-PEG data structure is useful for our problem because, starting from a
root vertex at the pursuers’ initial positions, executing a sequence of
AddSample operations can eventually lead to a vertex being marked with an all-
zero reachable shadow label. From there, a sequence of JPCs solving the
problem can readily be extracted by walking backward along through the graph.

###  IV-B Dropping a robot

Suppose $k$ pursuers are at some JPC $q$ with shadow label $\ell$, and have
computed a sequence of future JPCs to visit that will solve the problem from
that point, eventually reaching JPC with an all-clear shadow label. How can we
use this information to construct a new solution that can be executed from
this point by only $k-1$ of these pursuers, removing one particular pursuer
from the solution? Notice that this scenario applies both to the case of a
failed pursuer (in which case $q$ and $\ell$ can be derived from the current
state when the failure occurred, and $\ell$ may mark some shadows as clear)
and to a complete solution starting from the pursuers’ starting position and
all-contaminated shadow label. To simplify the notation below, we assume
without loss of generality that $n^{\text{th}}$ pursuer is the one removed.

The DropRobot method, shown in Algorithm 1, solves this problem. The algorithm
constructs an SG-PEG $G_{k-1}$, starting with a root vertex at which the
$n^{\text{th}}$ pursuer has been removed and the shadow label has been updated
accordingly. From there, it adds a collection of _junction samples_ , designed
to recover information lost due to the removal of the $n^{\text{th}}$ pursuer
at each step of the existing solution. If $G_{k-1}$ does not contain a
solution after that step, DropRobot continues by inserting additional samples
called _web samples_ designed to provide good coverage, in the sense of
visibility, of the environment. The process continues until a solution is
found, or until some arbitrary timeout expires. Details about junction
sampling and web sampling appear below.

Algorithm 1 DropRobot($F,k,q_{1},\ldots,q_{m},\ell$)

1:An environment $F$; a positive integer $k$; a sequence $q_{1},\ldots,q_{m}$
of $k$-pursuer JPCs; a shadow label $\ell$ for $q_{1}$.

2:A sequence $q^{\prime}_{1},\ldots,q^{\prime}_{m^{\prime}}$ of
$(k-1)$-pursuer JPCs leading to an all clear shadow label at
$q^{\prime}_{m^{\prime}}$ or Failed.

3:$G_{k-1}\leftarrow$ new SG-PEG for $k-1$ pursuers

4:$\langle p_{1},\ldots,p_{k}\rangle\leftarrow q_{1}$

5:$r\leftarrow G_{k-1}.\textsc{AddRoot}(\langle p_{1},\ldots,p_{k-1}\rangle)$

6:$\ell^{\prime}\leftarrow\ell$ updated for the removal of $p_{n}$

7:$r.\textsc{AddReachable}(\ell^{\prime})$

8:for $i\leftarrow 1,\ldots,m$ do

9: AddJunctionSamples($k$, $G_{k-1}$, $q_{i}$)

10:while $G_{k-1}$ has no solution and time remains do

11: $q\leftarrow$ WebSample($G_{k-1}$)

12: $G.\textsc{addSample}(q)$

13:if $G_{k-1}$ has a solution then

14: return $G_{k-1}$.ExtractSolution()

15:else

16: return Failed

Algorithm 2 AddJunctionSamples($k$, $G_{k-1}$, $q$)

1:A positive integer $k$; an SG-PEG $G_{k-1}$ for $k-1$ pursuers; a
$k$-pursuer JPC $q$

2:No return value, but samples are added to $G_{k-1}$.

3:$\langle p_{1},\ldots,p_{k}\rangle\leftarrow q$

4:$G_{k-1}.\textsc{addSample}(\langle p_{1},\ldots,p_{n-1}\rangle)$

5:for $i\leftarrow 1,\ldots,n-1$ do

6: if
$V({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}p_{i}})\cap
V(p_{n})\neq\emptyset$ then

7: $z\leftarrow$ random point in
$V({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}p_{i}})\cap
V(p_{n})$

8: $G.\textsc{addSample}(\langle
p_{1},p_{2},\ldots,{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}z},\ldots,p_{n-1}\rangle)$

9: $G.\textsc{addSample}(\langle
p_{1},p_{2},\ldots,{\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}p_{n}},\ldots,p_{n-1}\rangle)$

####  IV-B1 Junction sampling

The objective in junction sampling is, informally, to add vertices and edges
to the SG-PEG that allow remaining pursuers to ‘fill in’ for the removed
robot, wherever possible. Figure 5 shows a simple example of a pursuer removed
from a JPC during DropRobot. In this example, the lower pursuer is removed,
leaving the bottom portion of the environment unobserved. Junction sampling
adds new samples that provide a path within the SG-PEG for the rightmost robot
to visit the site of this lower portion.

This process, called AddJunctionSamples, is formalized in Algorithm 2. In the
general case, the algorithm identifies a remaining pursuer at a position
$p_{i}$ for which the visibility polygon intersects the visibility polygon of
the position $p_{n}$ of the removed pursuer. When this relationship is
detected, we add a sample that places the $i^{\text{th}}$ pursuer in the
intersection of the visibility polygons (see Figure 5c) and another that
places the $i^{\text{th}}$ pursuer at the former location of the
$n^{\text{th}}$ pursuer (Figure 5d). This process is repeated for each $i$
and, via repeated calls to AddJunctionSamples, each step of the previous
$k$-pursuer solution.

((a)) The initial JCP. The $n^{\text{th}}$ pursuer is blue [bottom], and the
$i^{\text{th}}$ pursuer is red [right].

((b)) The first sample to be added. The $n^{\text{th}}$ pursuer is removed
(Algorithm 2, line 4).

((c)) The second sample. The $n^{\text{th}}$ pursuer is removed and the
$i^{\text{th}}$ pursuer moves to a random point in
$V({\color[rgb]{.75,0,.25}\definecolor[named]{pgfstrokecolor}{rgb}{.75,0,.25}p_{i}})\cap
V({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}p_{n})}$.
(Algorithm 2, line 8).

((d)) The third sample. The $n^{\text{th}}$ pursuer is removed and the
$i^{\text{th}}$ pursuer takes its place. (Algorithm 2, line 9).

Figure 5: An example of junction sampling.

####  IV-B2 Web sampling

Though the structures introduced by junction sampling may be sufficient to
build a SG-PEG that can generate a solution with $k-1$ pursuers, such success
cannot be guaranteed. Therefore, after exhausting the junction samples,
Algorithm 1 continues with a broader sampling strategy called web sampling.
Web sampling was originally proposed for the failure-free version of the
problem [21].

((a)) A set of 35 samples that form one complete web.

((b)) 25000 samples drawn using web sampling. Notice how the points from $A$
(red) are biased towards the outer hooks, while the points from $B$ (blue)
favor the regions connecting adjacent hooks.

Figure 6: An illustration of web sampling.

The sampling approach is based on an underlying notion of a _web_. The
intuition is select a collection of positions that can see the entire
environment while also forming a connected graph via straight-line connections
within $F$. Generating a web occurs in two stages. First, we draw a collection
of points $A=\\{a_{1},a_{2},\dots,a_{n}\\}\subset F$ which provide full
visibility of the environment, i.e. $\bigcup_{1\leq i\leq n}V(a_{i})=F$. This
is done incrementally, by drawing samples from the unseen portion if $F$ until
all of $F$ is seen by some point in $A$. The second stage generates an
intersection set $B$ as follows. For each pair of distinct points
$a_{i},a_{j}\in A$, if $V(a_{i})\cap V(a_{j})\neq\emptyset$, we add a point
$b\in V(a_{i})\cap V(a_{j})$ to $B$. The combination $A\cup B$ forms one
complete web; those points are utilized in a randomly shuffled order. See
Figure 6.

To use these webs within WebSample (recall line 11 in Algorithm 1), we
generate one web for each of the $k-1$ pursuers. Then select a random vertex
$v$ from $G_{k-1}$ and, for two of the robots in that JPC, form a new sample
by replacing the existing positions with positions drawn (without replacement)
from those pursuers’ respective webs. If any web ever has no more points to
choose from, we generate new webs for each pursuer and continue the process.

###  IV-C Planning, execution, and replanning

Armed with the DropRobot method, we can consider how to use that algorithm for
the overall problem.

####  IV-C1 Generating the initial solution

To begin, we must generate an initial solution that the full complement of $n$
robots can begin to execute. First, we generate a trivial solution, namely a
strategy where no movement is required by the pursuers because their
visibility polygons fully cover the environment. We do so by iteratively
adding pursuers at random unseen locations until no shadows remain. This
single JPC becomes our trivial solution.

Note, however —recalling that only $n$ robots are available at the start—,
that it is rather likely that the trivial solution will require more than $n$
robots. If so, we repeatedly apply DropRobot, selecting the pursuer to remove
at random, until a solution requiring only $n$ pursuers has been formed. The
pursuer team then begins to execute this strategy.111It is possible in
principle that the trivial solution may require $n$ robots or less. In that
case, we can ignore any additional robots beyond the $m$ that are required for
the trivial solution and simply ‘execute’ the trivial solution.

####  IV-C2 Replanning after pursuer failures

If, during the execution of the search, a pursuer fails for some reason, a
replanning operation is required. In that case, we pause the pursuers’
movement until a new solution with one fewer pursuer is generated. This new
solution may be generated directly by DropRobot. Notice that the inputs to
that algorithm include the current state of the search (including the current
JPC and the current shadow label), which are leveraged to replan more rapidly
than planning from scratch each time. Once a new solution is computed, the
pursuers resume their search.

##  V Evaluation

((a)) An initial solution with 5 pursuers.

((b)) The problem state right before the green pursuer fails.

((c)) The new solution paths generated after the green pursuer fails.

((d)) The problem state right before the orange pursuer fails.

((e)) The new solution paths generated after the orange pursuer fails.

Figure 7: Snapshots of our algorithm through a single successful execution
($n=5,m=2$).

We implemented our algorithm in C++ and executed the code on an Ubuntu 20.04
laptop equipped with an Intel i7-10510U CPU and 16GB of RAM.

An example execution is illustrated in Figure 7. First, an initial solution is
generated (Figure 7a). Next, Figures 7b,c represent the input and output of
Algorithm 1 when the green pursuer malfunctions. Similarly, Figures 7d,e show
the state before and after the failure of the orange pursuer.

We simulated teams initially consisting of $n=5$ pursuers222Increasing $n$ has
a positive effect on the planning time of the proposed algorithm, since, by
construction, we need to generate solutions for each number of pursuers
between the number of pursuer in the trivial solution and $n$. In contrast,
OTSO21 can struggle with larger values of $n$ due to the increased complexity
of the joint configuration space, making it more difficult to connect pursuer
configurations. Thus, we hold $n$ fixed at 5 to enable a fair comparison. in
three different environments, depicted in Figures 3, 4, and 6. These
environments were selected because they highlight several interesting
attributes, such as hard to reach corners, narrow corridors, and evenly spaced
obstacles. Additionally, these environments allow us to more directly compare
against existing results. In particular, we compare the algorithm presented in
Section IV (‘this paper’) against our previous algorithm [21] (‘OTSO21’),
which was designed for the failure-free setting, as a baseline. During each
execution, we simulated $m$ pursuer failures. For each failure, a randomly-
selected pursuer was removed when the pursuers had completed a percentage
$\beta$ of their planned paths. For OTSO21, the algorithm was executed from
scratch for the initial solution and at each robot failure. Runs were
conducted for all four combinations of $m\in\\{2,3\\}$ and
$\beta\in\\{30\%,70\%\\}$.

Each trial was limited to at most 10 minutes of run time, including both
planning time and (simulated) execution time. If, after that time, the robots
had not yet successfully cleared all shadows, the simulation would have been
considered a failure. In the results presented here, none of the trials
failed.

For each combination of environment, algorithm, team size $n$, number of
failures $m$, and failure time $\beta$, we conducted 25 trials. The success or
failure of the run and total computation time spent planning and replanning
were recorded. Planning time is summarized by the mean $(\mu)$ and the
standard deviation $(\sigma)$ over all trials. Tables I and II report the
results, from which a few conclusions may be drawn.

_Replanning is beneficial_ Recall from Section IV-B1 that junction sampling
was developed to “recover” information in the event of a pursuer failure. The
notable improvements for the proposed algorithm compared to OTSO21 in the
environments of Figure 3 and Figure 4 can be attributed to efficiencies gained
by re-planning rather than starting from scratch. In the environment of Figure
6, the proposed algorithm performed similarly to OTSO21, likely due to the
complexity of the environment resulting in a high number of pursuers in its
trivial solutions and subsequently more calls to DropRobot to reach the
initial solution.

_Later failures are easier to recover_ For the trials with $\beta=70\%$, the
total planning time was less than when $\beta=30\%$. This is likely due to the
fact that allowing more time to traverse the solution path will, in many
cases, provide the next planning stage with an improved shadow label (i.e.
more cleared shadows), reducing the difficulty of the replanning problem.

_Impacts of the number of failures_ Increasing from $m=2$ to $m=3$ increased
the planning time for both algorithms. We speculate that this can be
attributed to the additional pursuer failure for which both the proposed
algorithm and OTSO21 are required to recompute strategies.

Table I: Simulation results for $n=5$ initial pursuers and $m=2$ failures.

| success | planning time (s)
---|---|---
| rate | $\mu$ | $\sigma$
Figure 3 |  |  |
This paper ($\beta=30\%$) | 100% | 46.09 | 21.50
OTSO21 ($\beta=30\%$) | 100% | 99.57 | 65.03
This paper ($\beta=70\%$) | 100% | 32.46 | 14.84
OTSO21 ($\beta=70\%$) | 100% | 89.36 | 59.62
Figure 4 |  |  |
This paper ($\beta=30\%$) | 100% | 6.47 | 7.46
OTSO21 ($\beta=30\%$) | 100% | 56.13 | 17.20
This paper ($\beta=70\%$) | 100% | 5.07 | 5.97
OTSO21 ($\beta=70\%$) | 100% | 52.87 | 17.59
Figure 6 |  |  |
This paper ($\beta=30\%$) | 100% | 89.13 | 39.08
OTSO21 ($\beta=30\%$) | 100% | 94.79 | 27.95
This paper ($\beta=70\%$) | 100% | 72.06 | 34.17
OTSO21 ($\beta=70\%$) | 100% | 73.98 | 20.56

Table II: Simulation results for $n=5$ initial pursuers and $m=3$ failures.

| success | planning time (s)
---|---|---
| rate | $\mu$ | $\sigma$
Figure 3 |  |  |
This paper ($\beta=30\%$) | 100% | 63.92 | 29.89
OTSO21 ($\beta=30\%$) | 100% | 117.90 | 64.78
This paper ($\beta=70\%$) | 100% | 39.88 | 20.61
OTSO21 ($\beta=70\%$) | 100% | 102.57 | 63.03
Figure 4 |  |  |
This paper ($\beta=30\%$) | 100% | 8.77 | 8.20
OTSO21 ($\beta=30\%$) | 100% | 58.35 | 16.60
This paper ($\beta=70\%$) | 100% | 6.54 | 6.41
OTSO21 ($\beta=70\%$) | 100% | 53.78 | 16.64
Figure 6 |  |  |
This paper ($\beta=30\%$) | 100% | 112.19 | 39.02
OTSO21 ($\beta=30\%$) | 100% | 108.11 | 30.13
This paper ($\beta=70\%$) | 100% | 74.81 | 35.71
OTSO21 ($\beta=70\%$) | 100% | 77.03 | 19.77

##  VI Conclusion

We presented a method of deconstructing higher dimensional solutions in order
to alleviate the issue of potential robotic failures in a visibility-based
pursuit-evasion problem. We did this by building a new sampling strategy which
allowed us to utilize previously computed information. Our algorithm was able
to greatly our-perform existing algorithms in the context of our problem.
Future work could include generating solutions that are intentionally robust
to failures. That is, a solution that would still be a solution if a limited
number of pursuers were to completely malfunction. One possible approach to
this problem would be to expand the shadow labels from single
clear/contaminated bits, to a richer representation of the sets of pursuer
failures under which that shadow would nonetheless be clear.

[sorting=nyt]

## References

  * [1] T.. Abramovskaya and N.. Petrov  “The theory of guaranteed search on graphs”  In _Vestnik St. Petersburg University_ 46.2, 2013, pp. 49–75
  * [2] Jose J. Acevedo, Begoña C. Arrue, Ivan Maza and Anibal Ollero  “A Decentralized Algorithm for Area Surveillance Missions Using a Team of Aerial Robots with Different Sensing Capabilities”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2014
  * [3] B. Alspach  “Searching and sweeping graphs: a brief survey”  In _Matematiche_ 59, 2004, pp. 5–37
  * [4] D. Bhadauria, K. Klein, V. Isler and S. Suri  “Capturing an Evader in Polygonal Environments with Obstacles: The Full Visibility Case”  In _International Journal of Robotics Research_ 31, 2012, pp. 1176–1189
  * [5] R. Borie, S. Koenig and C. Tovey  “Pursuit-Evasion Problems”  In _Handbook of Graph Theory_ ChapmanHall, 2013, pp. 1145–1165
  * [6] Jie Chen, Wenzhong Zha, Zhihong Peng and Dongbing Gu  “Multi-player pursuit–evasion games with one superior evader”  In _Automatica_ 71, 2016, pp. 24–32
  * [7] Philip Dames, Pratap Tokekar and Vijay Kumar  “Detecting, localizing, and tracking an unknown number of moving targets using a team of mobile robots”  In _International Journal of Robotics Research_ 36.13-14, 2017, pp. 1540–1553
  * [8] Joseph W. Durham, Antonio Franchi and Francesco Bullo  “Distributed pursuit-evasion without mapping or global localization via local frontiers”  In _Autonomous Robots_ 32, 2012, pp. 81–95
  * [9] P. Golovach  “A Topological Invariant in Pursuit Problems”  In _Differentsial’nye Uraveniya (Differential Equations)_ 25, 1989, pp. 923–929
  * [10] Livia Gregorin et al.  “Heuristics for the Multi-Robot Worst-Case Pursuit-Evasion Problem”  In _IEEE Access_ 5, 2017, pp. 17552–17566
  * [11] L.. Guibas et al.  “Visibility-Based Pursuit-Evasion in a Polygonal Environment”  In _International Journal on Computational Geometry and Applications_ 9.5, 1999, pp. 471–494
  * [12] Y.. Ho, A. Bryson and S. Baron  “Differential games and optimal pursuit-evasion strategies”  In _IEEE Trans. Automatic Control_ 10, 1965, pp. 385–389
  * [13] G. Hollinger, A. Kehagias and S. Singh  “Probabilistic Strategies for Pursuit in Cluttered Environments with Multiple Robots”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2007
  * [14] R. Isaacs  “Differential Games”  New York: Wiley, 1965
  * [15] Volkan Isler et al.  “Finding and tracking targets in the wild: Algorithms and field deployments”  In _Proc. IEEE International Symposium on Safety, Security, and Rescue Robotics_ , 2015
  * [16] A. Kolling and S. Carpin  “Multi-robot pursuit-evasion without maps”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2010
  * [17] Andreas Kolling and Stefano Carpin  “Pursuit-Evasion on Trees by Robot Teams”  In _IEEE Trans. Robotics_ 26, 2010, pp. 32–47  DOI: 10.1109/TRO.2009.2035737
  * [18] Sergey S. Kumkov, Stéphane Le Ménec and Valerii S. Patsko  “Zero-Sum Pursuit-Evasion Differential Games with Many Objects: Survey of Publications”  In _Dynamic Games and Applications_ 7, 2017, pp. 609–633
  * [19] Alberto Quattrini Li, Francesco Amigoni, Raffaele Fioratto and Volkan Isler  “A search-based approach to solve pursuit-evasion games with limited visibility in polygonal environments”  In _Proc. International Conference on Autonomous Agents and Multiagent Systems_ , 2018, pp. 1693–1701
  * [20] Alexander Von Moll, David Casbeer, Eloy Garcia and Dejan Milutinovic  “Pursuit-evasion of an Evader by Multiple Pursuers”  In _Proc. International Conference on Unmanned Aircraft Systems_ , 2018, pp. 133–142
  * [21] Trevor Olsen, Anne M. Tumlin, Nicholas M. Stiffler and Jason M. O’Kane  “A Visibility Roadmap Sampling Approach for a Multi-Robot Visibility-Based Pursuit-Evasion Problem” To appear  In _Proc. IEEE International Conference on Robotics and Automation_ , 2021
  * [22] S. Park, J. Lee and K. Chwa  “Visibility-Based Pursuit-Evasion in a Polygonal Region by a Searcher”  In _Proc. International Colloquium on Automata, Languages and Programming_ , 2001, pp. 281–290
  * [23] T.. Parsons  “Pursuit-Evasion in a Graph”  In _Theory and Application of Graphs_ Berlin: Springer-Verlag, 1976, pp. 426–441
  * [24] N.. Petrov  “The Cossack-robber differential game”  In _Differentsial’nye Uraveniya (Differential Equations)_ 19, 1983, pp. 1366–1374
  * [25] U. Ruiz and R. Murrieta-Cid  “Time-Optimal Motion Strategies for Capturing an Omnidirectional Evader using a Differential Drive Robot”  In _IEEE Trans. Robotics_ 21.3, 2013
  * [26] Florian Shkurti and Gregory Dudek  “On the complexity of searching for an evader with a faster pursuer”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2013, pp. 4062–4067  DOI: 10.1109/ICRA.2013.6631150
  * [27] Florian Shkurti and Gregory Dudek  “Topologically distinct trajectory predictions for probabilistic pursuit”  In _Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2017, pp. 5653–5660  DOI: 10.1109/IROS.2017.8206454
  * [28] Florian Shkurti, Nikhil Kakodkar and Gregory Dudek  “Model-Based Probabilistic Pursuit via Inverse Reinforcement Learning”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2018, pp. 7804–7811  DOI: 10.1109/ICRA.2018.8463196
  * [29] N.. Stiffler and J.. O’Kane  “A Complete Algorithm for Visibility-Based Pursuit-Evasion with Multiple Pursuers”  In _Proc. IEEE International Conference on Robotics and Automation_ , 2014
  * [30] N.. Stiffler and J.. O’Kane  “A Sampling Based Algorithm for Multi-Robot Visibility-Based Pursuit-Evasion”  In _Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2014
  * [31] N.. Stiffler and J.. O’Kane  “Complete and Optimal Visibility-Based Pursuit-Evasion”  In _International Journal of Robotics Research_ 36, 2017, pp. 923–946
  * [32] Nicholas M. Stiffler and Jason M. O’Kane  “Planning for robust visibility-based pursuit-evasion”  In _Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems_ , 2020  DOI: 10.1109/IROS45743.2020.9341031
  * [33] I. Suzuki and M. Yamashita  “Searching for a Mobile Intruder in a Polygonal Region”  In _SIAM Journal on Computing_ 21.5, 1992, pp. 863–888
  * [34] Pratap Tokekar, Deepak Bhadauria, Andrew Studenski and Volkan Isler  “A Robotic System for Monitoring carp in Minnesota Lakes”  In _Journal of Field Robotics_ 27.3, 2010, pp. 681–685
  * [35] B. Tovar and S.. LaValle  “Visibility-based Pursuit-Evasion with Bounded Speed”  In _International Journal of Robotics Research_ 27, 2008, pp. 1350–1360
  * [36] J. Vander Hook and V. Isler  “Pursuit and Evasion with Uncertain Bearing Measurements”  In _Proc. Candadian Conference on Computational Geometry_ , 2014
  * [37] Yuanda Wang, Lu Dong and Changyin Sun  “Cooperative control for multi-player pursuit-evasion games with reinforcement learning”  In _Neurocomputing_ 412, 2020, pp. 101–114
  * [38] Zhengyuan Zhou et al.  “Cooperative pursuit with Voronoi partitions”  In _Automatica_ 72, 2016, pp. 64–72
  * [39] Rui Zou and Sourabh Bhattacharya  “On Optimal Pursuit Trajectories for Visibility-Based Target Tracking Game”  In _IEEE Trans. Robotics_ 35(2), 2019, pp. 449–465


# Multi-turn Dialogue Response Generation in an
Adversarial Learning Framework

Oluwatobi Olabiyi
Capital One Conversation Research
Vienna VA
<EMAIL_ADDRESS>
&Alan Salimov
Capital One Conversation Research
San Francisco CA
<EMAIL_ADDRESS>
Anish Khazane
Capital One Conversation Research
San Francisco CA
<EMAIL_ADDRESS>
&Erik T. Mueller
Capital One Conversation Research
Vienna VA
<EMAIL_ADDRESS>

###### Abstract

We propose an adversarial learning approach for generating multi-turn dialogue
responses. Our proposed framework, hredGAN, is based on conditional generative
adversarial networks (GANs). The GAN’s generator is a modified hierarchical
recurrent encoder-decoder network (HRED) and the discriminator is a word-level
bidirectional RNN that shares context and word embeddings with the generator.
During inference, noise samples conditioned on the dialogue history are used
to perturb the generator’s latent space to generate several possible
responses. The final response is the one ranked best by the discriminator. The
hredGAN shows improved performance over existing methods: (1) it generalizes
better than networks trained using only the log-likelihood criterion, and (2)
it generates longer, more informative and more diverse responses with high
utterance and topic relevance even with limited training data. This
improvement is demonstrated on the Movie triples and Ubuntu dialogue datasets
using both automatic and human evaluations.

##  1 Introduction

Recent advances in deep neural network architectures have enabled tremendous
success on a number of difficult machine learning problems. While these
results are impressive, producing a deployable neural network–based model that
can engage in open domain conversation still remains elusive. A dialogue
system needs to be able to generate meaningful and diverse responses that are
simultaneously coherent with the input utterance and the overall dialogue
topic. Unfortunately, earlier conversation models trained with naturalistic
dialogue data suffered greatly from limited contextual information (Sutskever
et al., 2014; Vinyals and Le, 2015) and lack of diversity (Li et al., 2016a).
These problems often lead to generic and safe responses to a variety of input
utterances.

Serban et al. (2016) and Xing et al. (2017) proposed the Hierarchical
Recurrent Encoder-Decoder (HRED) network to capture long temporal dependencies
in multi-turn conversations to address the limited contextual information but
the diversity problem remained. In contrast, some HRED variants such as
variational (Serban et al., 2017b) and multi-resolution (Serban et al., 2017a)
HREDs attempt to alleviate the diversity problem by injecting noise at the
utterance level and by extracting additional context to condition the
generator on. While these approaches achieve a certain measure of success over
the basic HRED, the generated responses are still mostly generic since they do
not control the generator’s output. This is because the output conditional
distribution is not calibrated. Li et al. (2016a), on the other hand, consider
a diversity promoting training objective but their model is for single turn
conversations and cannot be trained end-to-end.

The generative adversarial network (GAN) (Goodfellow et al., 2014) seems to be
an appropriate solution to the diversity problem. GAN matches data from two
different distributions by introducing an adversarial game between a generator
and a discriminator. We explore hredGAN: conditional GANs for multi-turn
dialogue models with an HRED generator and discriminator. hredGAN combines
ideas from both generative and retrieval-based multi-turn dialogue systems to
improve their individual performances. This is achieved by sharing the context
and word embeddings between the generator and the discriminator allowing for
joint end-to-end training using back-propagation. To the best of our
knowledge, no existing work has applied conditional GANs to multi-turn
dialogue models and especially not with HRED generators and discriminators. We
demonstrate the effectiveness of hredGAN over the VHRED for dialogue modeling
with evaluations on the Movie triples and Ubuntu technical support datasets.

##  2 Related Work

Our work is related to end-to-end neural network–based open domain dialogue
models. Most neural dialogue models use transduction frameworks adapted from
neural machine translation (Sutskever et al., 2014; Bahdanau et al., 2015).
These Seq2Seq networks are trained end-to-end with MLE criteria using large
corpora of human-to-human conversation data. Others use GAN’s discriminator as
a reward function in a reinforcement learning framework (Yu et al., 2017) and
in conjunction with MLE (Li et al., 2017; Che et al., 2017). Zhang et al.
(2017) explored the idea of GAN with a feature matching criterion. Xu et al.
(2017) and Zhang et al. (2018) employed GAN with an approximate embedding
layer as well as with adversarial information maximization respectively to
improve Seq2Seq’s diversity performance.

Still, Seq2Seq models are limited in their ability to capture long temporal
dependencies in multi-turn conversation. Although Li et al. (2016b) attempted
to optimize a pair of Seq2Seq models for multi-turn dialogue, the multi-turn
objective is only applied at inference and not used for actual model training.
Hence the introduction of HRED models (Serban et al., 2016, 2017a, 2017b; Xing
et al., 2017) for modeling dialogue response in multi-turn conversations.
However, these HRED models suffer from lack of diversity since they are only
trained with MLE criteria. On the other hand, adversarial system has been used
for evaluating open domain dialogue models (Bruni and Fernández, 2018; Kannan
and Vinyals, 2017). Our work, hredGAN, is closest to the combination of HRED
generation models (Serban et al., 2016) and adversarial evaluation (Kannan and
Vinyals, 2017).

##  3 Model

###  3.1 Adversarial Learning of Dialogue Response

Consider a dialogue consisting of a sequence of $N$ utterances,
$\boldsymbol{x}=\big{(}x_{1},x_{2},\cdots,x_{N}\big{)}$, where each utterance
$x_{i}=\big{(}x_{i}^{1},x_{i}^{2},\cdots,x_{i}^{M_{i}}\big{)}$ contains a
variable-length sequence of $M_{i}$ word tokens such that ${x_{i}}^{j}\in V$
for vocabulary $V$. At any time step $i$, the dialogue history is given by
$\boldsymbol{x_{i}}=\big{(}x_{1},x_{2},\cdots,x_{i}\big{)}$. The dialogue
response generation task can be defined as follows: Given a dialogue history
$\boldsymbol{x_{i}}$, generate a response
$y_{i}=\big{(}y_{i}^{1},y_{i}^{2},\cdots,y_{i}^{T_{i}}\big{)}$, where $T_{i}$
is the number of generated tokens. We also want the distribution of the
generated response $P(y_{i})$ to be indistinguishable from that of the ground
truth $P(x_{i+1})$ and $T_{i}=M_{i+1}$. Conditional GAN learns a mapping from
an observed dialogue history, $\boldsymbol{x_{i}}$, and a sequence of random
noise vectors, $z_{i}$ to a sequence of output tokens, $y_{i}$,
$G:\\{\boldsymbol{x_{i}},z_{i}\\}\rightarrow y_{i}$. The generator $G$ is
trained to produce output sequences that cannot be distinguished from the
ground truth sequence by an adversarially trained discriminator $D$ that is
trained to do well at detecting the generator’s fakes. The distribution of the
generator output sequence can be factored by the product rule:

$\displaystyle
P(y_{i}|\boldsymbol{x_{i}})=P(y_{i}^{1})\prod_{j=2}^{T_{i}}P\big{(}y_{i}^{j}|y_{i}^{1},\cdots,y_{i}^{j-1},\boldsymbol{x_{i}}\big{)}$
(1) $\displaystyle
P\big{(}y_{i}^{j}|y_{i}^{1},\cdots,y_{i}^{j-1},\boldsymbol{x_{i}}\big{)}=P_{\theta_{G}}\big{(}y_{i}^{1:j-1},\boldsymbol{x_{i}}\big{)}$
(2)

where $y_{i}^{i:j-1}=(y_{i}^{1},\cdots,y_{i}^{j-1})$ and $\theta_{G}$ are the
parameters of the generator model.
$P_{\theta_{G}}\big{(}y_{i}^{i:j-1},\boldsymbol{x_{i}}\big{)}$ is an
autoregressive generative model where the probability of the current token
depends on the past generated sequence. Training the generator $G$ with the
log-likelihood criterion is unstable in practice, and therefore the past
generated sequence is substituted with the ground truth, a method known as
teacher forcing (Williams and Zipser, 1989), i.e.,

$P\big{(}y_{i}^{j}|y_{i}^{1},\cdots,y_{i}^{j-1},\boldsymbol{x_{i}}\big{)}\approx
P_{\theta_{G}}\big{(}x_{i+1}^{1:j-1},\boldsymbol{x_{i}}\big{)}$ (3)

Using (3) in relation to GAN, we define our fake sample as the teacher forcing
output with some input noise $z_{i}$

$y_{i}^{j}\sim
P_{\theta_{G}}\big{(}x_{i+1}^{1:j-1},\boldsymbol{x_{i}},z_{i}\big{)}$ (4)

and the corresponding real sample as ground truth $x_{i+1}^{j}$.

With the GAN objective, we can match the noise distribution, $P(z_{i})$, to
the distribution of the ground truth response,
$P(x_{i+1}|\boldsymbol{x_{i}})$. Varying the noise input then allows us to
generate diverse responses to the same dialogue history. Furthermore, the
discriminator, since it is calibrated, is used during inference to rank the
generated responses, providing a means of controlling the generator output.

####  3.1.1 Objectives

The objective of a conditional GAN can be expressed as

$\mathcal{L}_{cGAN}(G,D)=\mathbb{E}_{\boldsymbol{x_{i}},x_{i+1}}[\log~{}D(x_{i+1},\boldsymbol{x_{i}})]+\\\
\mathbb{E}_{\boldsymbol{x_{i}},z_{i}}[1-\log{}D(G(\boldsymbol{x_{i}},z_{i}),\boldsymbol{x_{i}})]$
(5)

where $G$ tries to minimize this objective against an adversarial $D$ that
tries to maximize it:

$G^{*},D^{*}=arg\mathop{min}\limits_{G}\mathop{max}\limits_{D}\mathcal{L}_{cGAN}(G,D).$
(6)

Previous approaches have shown that it is beneficial to mix the GAN objective
with a more traditional loss such as cross-entropy loss (Lamb et al., 2016; Li
et al., 2017). The discriminator’s job remains unchanged, but the generator is
tasked not only to fool the discriminator but also to be near the ground truth
$x_{i+1}$ in the cross-entropy sense:

$\mathcal{L}_{MLE}(G)=\mathbb{E}_{\boldsymbol{x_{i}},x_{i+1},z_{i}}[-log~{}P_{\theta_{G}}\big{(}x_{i+1},\boldsymbol{x_{i}},z_{i}\big{)}].$
(7)

Our final objective is,

$G^{*},D^{*}=arg\mathop{min}\limits_{G}\mathop{max}\limits_{D}\big{(}\lambda_{G}\mathcal{L}_{cGAN}(G,D)+\\\
\lambda_{M}\mathcal{L}_{MLE}(G)\big{)}.$ (8)

It is worth mentioning that, without $z_{i}$, the net could still learn a
mapping from $\boldsymbol{x_{i}}$ to $y_{i}$, but it would produce
deterministic outputs and fail to match any distribution other than a delta
function (Isola et al., 2017). This is one key area where our work is
different from Lamb et al.’s and Li et al.’s. The schematic of the proposed
hredGAN is depicted at the right hand side of Figure 1.

Figure 1: Left: The hredGAN architecture - The generator makes predictions
conditioned on the dialogue history, $\boldsymbol{h_{i}}$, attention,
$a_{i}^{j}$, noise sample, $z_{i}^{j}$, and ground truth, $x_{i+1}^{j-1}$.
Right: RNN-based discriminator that discriminates bidirectionally at the word
level.

####  3.1.2 Generator

We adopted an HRED dialogue generator similar to Serban et al. (2016, 2017a,
2017b) and Xing et al. (2017). The HRED contains three recurrent structures,
i.e. the encoder $(eRNN)$, context $(cRNN)$, and decoder $(dRNN)$ RNN. The
conditional probability modeled by the HRED per output word token is given by

$P_{\theta_{G}}\big{(}y_{i}^{j}|x_{i+1}^{1:j-1},\boldsymbol{x_{i}}\big{)}=dRNN\big{(}E(x_{i+1}^{j-1}),h_{i}^{j-1},\boldsymbol{h_{i}}\big{)}$
(9)

where $E(.)$ is the embedding lookup,
$\boldsymbol{h_{i}}=cRNN(eRNN(E(x_{i}),\boldsymbol{h_{i-1}})$, $eRNN(.)$ maps
a sequence of input symbols into fixed-length vector, and $h$ and
$\boldsymbol{h}$ are the hidden states of the decoder and context RNN,
respectively.

In the multi-resolution HRED, (Serban et al., 2017a), high-level tokens are
extracted and processed by another RNN to improve performance. We circumvent
the need for this extra processing by allowing the decoder to attend to
different parts of the input utterance during response generation (Bahdanau et
al., 2015; Luong et al., 2015). We introduce a local attention into (9) and
encode the attention memory differently from the context through an attention
encoder RNN $(aRNN)$, yielding:

$P_{\theta_{G}}\big{(}y_{i}^{j}|x_{i+1}^{1:j-1},\boldsymbol{x_{i}}\big{)}=\\\
dRNN\big{(}E(x_{i+1}^{j-1}),h_{i}^{j-1},a_{i}^{j},\boldsymbol{h_{i}}\big{)}$
(10)

where
$a_{i}^{j}=\sum_{m=1}^{M_{i}}\frac{exp(\alpha_{m})}{\sum_{m=1}^{M_{i}}exp(\alpha_{m})}h_{i}^{{}^{\prime}m},$
$h_{i}^{{}^{\prime}m}=aRNN(E(x_{i}^{m}),h_{i}^{{}^{\prime}m-1})$,
$h^{{}^{\prime}}$ is the hidden state of the attention RNN, and $\alpha_{k}$
is either a logit projection of $(h_{i}^{j-1},h_{i}^{{}^{\prime}m})$ in the
case of Bahdanau et al. (2015) or $(h_{i}^{j-1})^{T}\cdot
h_{i}^{{}^{\prime}m}$ in the case of Luong et al. (2015). The modified HRED
architecture is shown in Figure 2.

Figure 2: The HRED generator with local attention - The attention RNN ensures
local relevance while the context RNN ensures global relevance. Their states
are combined to initialize the decoder RNN and the discriminator BiRNN.

Noise Injection: We inject Gaussian noise at the input of the decoder RNN.
Noise samples could be injected at the utterance or word level. With noise
injection, the conditional probability of the decoder output becomes

$P_{\theta_{G}}\big{(}y_{i}^{j}|x_{i+1}^{1:j-1},z_{i}^{j},\boldsymbol{x_{i}}\big{)}=\\\
dRNN\big{(}E(x_{i+1}^{j-1}),h_{i}^{j-1},a_{i}^{j},z_{i}^{j},\boldsymbol{h_{i}}\big{)}$
(11)

where $z_{i}^{j}\sim\mathcal{N}_{i}(0,\boldsymbol{I})$, for utterance-level
noise and $z_{i}^{j}\sim\mathcal{N}_{i}^{j}(0,\boldsymbol{I})$, for word-level
noise.

####  3.1.3 Discriminator

The discriminator shares context and word embeddings with the generator and
can discriminate at the word level (Lamb et al., 2016). The word-level
discrimination is achieved through a bidirectional RNN and is able to capture
both syntactic and conceptual differences between the generator output and the
ground truth. The aggregate classification of an input sequence, $\chi$ can be
factored over word-level discrimination and expressed as

$\displaystyle
D(\boldsymbol{x_{i}},\chi)=D(\boldsymbol{h_{i}},\chi)=\bigg{[}\prod_{j=1}^{J}D_{RNN}(\boldsymbol{h_{i}},E(\chi^{j}))\bigg{]}^{\frac{1}{J}}$
(12)

where $D_{RNN}(.)$ is the word discriminator RNN, $\boldsymbol{h_{i}}$ is an
encoded vector of the dialogue history $\boldsymbol{x_{i}}$ obtained from the
generator’s $cRNN(.)$ output, and $\chi^{j}$ is the jth word or token of the
input sequence $\chi$. $\chi=y_{i}$ and $J=T_{i}$ for the case of generator’s
decoder output, $\chi=x_{i+1}$ and $J=M_{i+1}$ for the case of ground truth.
The discriminator architecture is depicted on the left hand side of Figure 1.

###  3.2 Adversarial Generation of Multi-turn Dialogue Response

In this section, we describe the generation process during inference. The
generation objective can be mathematically described as

$y_{i}^{*}=arg\mathop{max}\limits_{l}\big{\\{}P(y_{i,l}|\boldsymbol{x_{i}})+D^{*}(\boldsymbol{x_{i}},y_{i,l})]\big{\\}}_{l=1}^{L}$
(13)

where $y_{i,l}=G^{*}(\boldsymbol{x_{i}},z_{i,l})$, $z_{i,l}$ is the lth noise
samples at dialogue step $i$, and $L$ is the number of response samples.
Equation 13 shows that our inference objective is the same as the training
objective (8), combining both the MLE and adversarial criteria. This is in
contrast to existing work where the discriminator is usually discarded during
inference.

The inference described by (13) is intractable due to the enormous search
space of $y_{i,l}$. Therefore, we turn to an approximate solution where we use
greedy decoding (MLE) on the first part of the objective function to generate
$L$ lists of responses based on noise samples $\\{z_{i,l}\\}_{l=1}^{L}$. In
order to facilitate the exploration of the generator’s latent space, we sample
a modified noise distribution,
$z_{i,l}^{j}\sim\mathcal{N}_{i,l}(0,\alpha\boldsymbol{I})$, or
$z_{i,l}^{j}\sim\mathcal{N}_{i,l}^{j}(0,\alpha\boldsymbol{I})$ where
$\alpha>1.0$, is the exploration factor that increases the noise variance. We
then rank the $L$ lists using the discriminator score,
{$D^{*}(\boldsymbol{x_{i}},y_{i,l})]\big{\\}}_{l=1}^{L}$. The response with
the highest discriminator ranking is the optimum response for the dialogue
context.

0: A generator $G$ with parameters $\theta_{G}$.

0: A discriminator $D$ with parameters $\theta_{D}$.

for number of training iterations do

Initialize $cRNN$ to zero_state, $\boldsymbol{h_{0}}$

Sample a mini-batch of conversations, $\boldsymbol{x}=\\{x_{i}\\}_{i=1}^{N}$,
$\boldsymbol{x_{i}}=(x_{1},x_{2},\cdots,x_{i})$ with $N$ utterances. Each
utterance mini batch $i$ contains $M_{i}$ word tokens.

for $i=1$ to $N-1$ do

Update the context state.

$\boldsymbol{h_{i}}=cRNN(eRNN(E(x_{i})),\boldsymbol{h_{i-1}})$

Compute the generator output using (11).

$P_{\theta_{G}}\big{(}y_{i}|,z_{i},\boldsymbol{x_{i}}\big{)}=\big{\\{}P_{\theta_{G}}\big{(}y_{i}^{j}|x_{i+1}^{1:j-1},z_{i}^{j},\boldsymbol{x_{i}}\big{)}\big{\\}}_{j=1}^{M_{i+1}}$

Sample a corresponding mini batch of utterance $y_{i}$.

$y_{i}\sim P_{\theta_{G}}\big{(}y_{i}|,z_{i},\boldsymbol{x_{i}}\big{)}$

end for

Compute the discriminator accuracy $D_{acc}$ over $N-1$ utterances
$\\{y_{i}\\}_{i=1}^{N-1}$ and $\\{x_{i+1}\\}_{i=1}^{N-1}$

if $D_{acc}<acc_{D_{th}}$ then

Update $\theta_{D}$ with gradient of the discriminator loss.

$\sum\limits_{i}[\nabla_{\theta_{D}}\log{}D(\boldsymbol{h_{i}},x_{i+1})+\nabla_{\theta_{D}}log\big{(}1-D(\boldsymbol{h_{i}},y_{i})\big{)}]$

end if

if $D_{acc}<acc_{G_{th}}$ then

Update $\theta_{G}$ with the generator’s MLE loss only.

$\sum\limits_{i}[\nabla_{\theta_{G}}\log{}P_{\theta_{G}}\big{(}y_{i}|,z_{i},\boldsymbol{x_{i}}\big{)}]$

else

Update $\theta_{G}$ with both adversarial and MLE losses.

$\sum\limits_{i}[\lambda_{G}\nabla_{\theta_{G}}\log{}D(\boldsymbol{h_{i}},y_{i})+\lambda_{M}\nabla_{\theta_{G}}\log{}P_{\theta_{G}}\big{(}y_{i}|,z_{i},\boldsymbol{x_{i}}\big{)}]$

end if

end for

Algorithm 1 Adversarial Learning of hredGAN

##  4 Training of hredGAN

We trained both the generator and the discriminator simultaneously as
highlighted in Algorithm 1 with $\lambda_{G}=\lambda_{M}=1$. GAN training is
prone to instability due to competition between the generator and the
discriminator. Therefore, parameter updates are conditioned on the
discriminator performance (Lamb et al., 2016).

The generator consists of four RNNs with different parameters, that is,
$aRNN,eRNN,cRNN$, and $dRNN$. $aRNN$ and $eRNN$ are both bidirectional, while
$cRNN$ and $dRNN$ are unidirectional. Each RNN has 3 layers, and the hidden
state size is 512. The $dRNN$ and $aRNN$ are connected using an additive
attention mechanism (Bahdanau et al., 2015).

The discriminator shares $aRNN,eRNN$, and $cRNN$ with the generator. $D_{RNN}$
is a stacked bidirectional RNN with 3 layers and a hidden state size of 512.
The $cRNN$ states are used to initialize the states of $D_{RNN}$. The output
of both the forward and the backward cells for each word are concatenated and
passed to a fully-connected layer with binary output. The output is the
probability that the word is from the ground truth given the past and future
words of the sequence.

Others: All RNNs used are gated recurrent unit (GRU) cells (Cho et al., 2014).
The word embedding size is 512 and shared between the generator and the
discriminator. The initial learning rate is $0.5$ with decay rate factor of
$0.99$, applied when the adversarial loss has increased over two iterations.
We use a batch size of 64 and clip gradients around $5.0$. As in Lamb et al.
(2016), we find $acc_{D_{th}}=0.99$ and $acc_{G_{th}}=0.75$ to suffice. All
parameters are initialized with Xavier uniform random initialization (Glorot
and Bengio, 2010). The vocabulary size $V$ is $50,000$. Due to the large
vocabulary size, we use sampled softmax loss (Jean et al., 2015) for MLE loss
to expedite the training process. However, we use full softmax for evaluation.
The model is trained end-to-end using the stochastic gradient descent
algorithm.

##  5 Experiments and Results

We consider the task of generating dialogue responses conditioned on the
dialogue history and the current input utterance. We compare the proposed
hredGAN model against some alternatives on publicly available datasets.

###  5.1 Datasets

Movie Triples Corpus (MTC) dataset (Serban et al., 2016). This dataset was
derived from the Movie-DiC dataset by Banchs (2012). Although this dataset
spans a wide range of topics with few spelling mistakes, its small size of
only about 240,000 dialogue triples makes it difficult to train a dialogue
model, as pointed out by Serban et al. (2016). We thought that this scenario
would really benefit from the proposed adversarial generation.

Ubuntu Dialogue Corpus (UDC) dataset (Serban et al., 2017b). This dataset was
extracted from the Ubuntu Relay Chat Channel. Although the topics in the
dataset are not as diverse as in the MTC, the dataset is very large,
containing about 1.85 million conversations with an average of 5 utterances
per conversation.

We split both MTC and UDC into training, validation, and test sets, using 90%,
5%, and 5% proportions, respectively. We performed minimal preprocessing of
the datasets by replacing all words except the top 50,000 most frequent words
by an UNK symbol.

Model | Teacher Forcing | Autoregression | Human
---|---|---|---
Perplexity | $-logD(G(.))$ | BLEU-2 | ROUGE-2 | DISTINCT-1/2 | NASL | Evaluation
MTC |  |  |  |  |  |  |
HRED | 31.92/36.00 | NA | 0.0474 | 0.0384 | 0.0026/0.0056 | 0.535 | 0.2560 $\pm$ 0.0977
VHRED | 42.61/44.97 | NA | 0.0606 | 0.1181 | 0.0048/0.0163 | 0.831 | 0.3909 $\pm$ 0.0240
hredGAN_u | 23.57/23.54 | 6.85/6.81 | 0.0493 | 0.2416 | 0.0167/0.1306 | 0.884 | 0.5582 $\pm$ 0.0118
hredGAN_w | 24.20/24.14 | 13.35/13.40 | 0.0613 | 0.3244 | 0.0179/0.1720 | 1.540 | 0.7869 $\pm$ 0.1148
UDC |  |  |  |  |  |  |
HRED | 69.39/86.40 | NA | 0.0177 | 0.0483 | 0.0203/0.0466 | 0.892 | 0.3475 $\pm$ 0.1062
VHRED | 98.50/105.20 | NA | 0.0171 | 0.0855 | 0.0297/0.0890 | 0.873 | 0.4046 $\pm$ 0.0188
hredGAN_u | 56.82/57.32 | 10.09/10.08 | 0.0137 | 0.0716 | 0.0260/0.0847 | 1.379 | 0.6133 $\pm$ 0.0361
hredGAN_w | 47.73/48.18 | 8.37/8.36 | 0.0216 | 0.1168 | 0.0516/0.1821 | 1.098 | 0.6905 $\pm$ 0.0706
Table 1: Generator Performance Evaluation

###  5.2 Evaluation Metrics

Accurate evaluation of dialogue models is still an open challenge. In this
paper, we employ both automatic and human evaluations.

####  5.2.1 Automatic Evaluation

We employed some of the automatic evaluation metrics that are used in
probabilistic language and dialogue models, and statistical machine
translation. Although these metrics may not correlate well with human judgment
of dialogue responses (Liu et al., 2016), they provide a good baseline for
comparing dialogue model performance.

Perplexity \- For a model with parameter $\theta$, we define perplexity as:

$exp\bigg{[}-\frac{1}{N_{W}}\sum_{k=1}^{K}log~{}P_{\theta}(y_{1},y_{2},\dots,y_{N_{k}-1})\bigg{]}$
(14)

where $K$ is the number of conversations in the dataset, $N_{k}$ is the number
of utterances in conversation $k$, and $N_{W}$ is the total number of word
tokens in the entire dataset. The lower the perplexity, the better. The
perplexity measures the likelihood of generating the ground truth given the
model parameters. While a generative model can generate a diversity of
responses, it should still assign a high probability to the ground truth
utterance.

BLEU \- The BLEU score (Papineni et al., 2002) provides a measure of overlap
between the generated response (candidate) and the ground truth (reference)
using a modified n-gram precision. According to Liu et. al. (Liu et al.,
2016), BLEU-2 score is fairly correlated with human judgment for non-technical
dialogue (such as MTC).

ROUGE \- The ROUGE score (Lin, 2014) is similar to BLEU but it is recall-
oriented instead. It is used for automatic evaluation of text summarization
and machine translation. To compliment the BLEU score, we use ROUGE-N with
$N=2$ for our evaluation.

Distinct n-gram \- This is the fraction of unique n-grams in the generated
responses and it provides a measure of diversity. Models with higher a number
of distinct n-grams tend to produce more diverse responses (Li et al., 2016a).
For our evaluation, we use 1- and 2- grams.

Normalized Average Sequence Length (NASL) \- This measures the average number
of words in model-generated responses normalized by the average number of
words in the ground truth.

####  5.2.2 Human Evaluation

For human evaluation, we follow a similar setup as Li et al. (2016a),
employing crowd-sourced judges to evaluate a random selection of 200 samples.
We presented both the multi-turn context and the generated responses from the
models to 3 judges and asked them to rank the general response quality in
terms of relevance and informativeness. For $N$ models, the model with the
lowest quality is assigned a score 0 and the highest is assigned a score N-1.
Ties are not allowed. The scores are normalized between 0 and 1 and averaged
over the total number of samples and judges. For each model, we also estimated
the per sample score variance between judges and then averaged over the number
of samples, i.e., sum of variances divided by the square of number of samples
(assuming sample independence). The square root of result is reported as the
standard error of the human judgment for the model.

###  5.3 Baseline

We compare the performance of our model to (V)HRED (Serban et al., 2016,
2017b), since they are the closest to our approach in implementation and are
the current state of the art in open-domain dialogue models. HRED is very
similar to our proposed generator, but without the input utterance attention
and noise samples. VHRED introduces a latent variable to the HRED between the
cRNN and the dRNN and was trained using the variational lower bound on the
log-likelihood. The VHRED can generate multiple responses per context like
hredGAN, but it has no specific criteria for selecting the best response.

The HRED and VHRED models are both trained using the Theano-based
implementation obtained from https://github.com/julianser/hed-dlg-truncated.
The training and validation sets used for UDC and MTC dataset were obtained
directly from the authors111UDC was obtained from
http://www.iulianserban.com/Files/UbuntuDialogueCorpus.zip, and the link to
MTC was obtained privately. of (V)HRED. For model comparison, we use a test
set that is disjoint from the training and validation sets.

###  5.4 Results

We have two variants of hredGAN based on the noise injection approach, i.e.,
hredGAN with utterance-level (hredGAN_u) and word-level (hredGAN_w) noise
injections.

We compare the performance of these two variants with HRED and VHRED models.

Perplexity: The average perplexity per word performance of all the four models
on MTC and UDC datasets (validation/test) are reported in the first column on
Table 1. The table indicates that both variants of the hredGAN model perform
better than the HRED and VHRED models in terms of the perplexity measure.
However, using the adversarial loss criterion (Eq. (8)), the hredGAN_u model
performs better on MTC and worse on UDC. Note that, for this experiment, we
run all models in teacher forcing mode.

Generation Hyperparameter: For adversarial generation, we perform a linear
search for $\alpha$ between 1 and 20 at an increment of 1 using Eq. (13), with
sample size $L=64$, on validation sets with models run in autoregression. The
optimum values of $\alpha$ for hredGAN_u and hredGAN_w for UDC are $7.0$ and
$9.0$ respectively. The values for MTC are not convex, probably due to small
size of the dataset, so we use the same $\alpha$ values as UDC. We however
note that for both datasets, any integer value between 3 and 10 (inclusive)
works well in practice.

Item | $D(G(.))$ |  Utterance
---|---|---
MTC |  |
Context_0 | NA |  perhaps $<$person$>$ had a word with the man upstairs .
Context_1 | NA |  a word ? i ’ m sure by now he ’ s engineered a hostile takeover .
Response_0 | 0.996 |  $<$person$>$ , i know what you ’ re saying , $<$person$>$ , that ’ s not what i ’ m saying .
Response_1 | 0.991 |  $<$person$>$ , i know . i was just about to help the guy .
Response_2 | 0.315 |  $<$person$>$ , i ’ m sorry .
Response_3 | 0.203 |  $<$person$>$ , i ’ m a little out .
Context_0 | NA |  says he wanted food . $<$person$>$ . he wanted the gold .
Context_1 | NA |  how ’ s he going to want the gold ? he couldn ’ t even know we had it .
Response_0 | 0.998 |  $<$person$>$ , i know . but it ’ s not him , it ’ s the only way he ’ s got it all figured
Response_1 | 0.981 |  $<$person$>$ , i know . but i have to tell you . these things are really stupid and you think i was wrong ?
Response_2 | 0.690 |  $<$person$>$ , i ’ m sure he did .
Response_3 | 0.314 |  $<$person$>$ , i ’ m not sure .
UDC |  |
Context_0 | NA |  The netboot one is suppose to download packages from the net.
Context_1 | NA |  like the ones to be installed? or the installed to be run?
Response_0 | 0.993 |  you don ’ t need to install the whole system , just install the ubuntu installer
Response_1 | 0.952 |  you can install the ubuntu installer from the ubuntu menu
Response_2 | 0.749 |  I ’ m not sure , I don ’ t know .
Response_3 | 0.184 |  you can
Response_4 | 0.003 |  you a . 1 . . . . . . . . . . . . . . . . . . . . .
Context_0 | NA |  DJones: update manager won’t detect 12.04.1 as a new version if you are already running 12.04, because 12.04.1 = 12.04 + lots of package updates
Response_0 | 0.991 |  did you try a clean install of the latest version ?
Response_1 | 0.981 |  try installing the latest _UNK and see if it works
Response_2 | 0.615 |  I ’ m not sure you have a problem . . .
Response_3 | 0.191 |  try sudo apt-get remove the package that is not installed
Response_4 | 0.002 |  try the _UNK . 1 . 1 . 1 . 1 . 1 . _UNK . deb
Table 2: Example of Discriminator Ranking with hredGAN_w Movie |
---|---
Context_0 |  perhaps $<$person$>$ had a word with the man upstairs .
HRED |  i ’ m sorry , $<$person$>$ .
VHRED |  $<$person$<$ ’ t do it .
hredGAN_w |  $<$person$>$ , i ’ m not gon na be okay . i just don ’ t think it ’ s a good idea .
hredGAN_u |  $<$person$>$ , i cause it was all the way to you .
Context_1 |  a word ? i ’ m sure by now he ’ s engineered a hostile takeover .
HRED |  i ’ m sorry , $<$person$>$ .
VHRED |  $<$person$>$ ’ t do it .
hredGAN_w |  $<$person$>$ , i know what you ’ re saying , $<$person$>$ , that ’ s not what i ’ m saying .
hredGAN_u |  $<$person$>$ , i have to tell you i ’ m not the same .
Context_0 |  $<$person$>$ ’ s .
HRED |  i ’ m sorry , $<$person$>$ .
VHRED |  $<$person$>$ ’ t do it .
hredGAN_w |  $<$person$>$ , i ’ m sure it ’ s the only thing i ever imagined .
hredGAN_u |  $<$person$>$ , i ’ ll be right there .
Context_1 |  can i ask you something about her ?
HRED |  i don ’ t know .
VHRED: |  you ’ re not going to be here .
hredGAN_w |  i don ’ t know . i think i ’ ve heard of it .
hredGAN_u |  i ’ m sorry , i can ’ t .
Ubuntu |
Context_0 |  this is Dacs i am in i used ’sudo statx and it let me in
HRED |  what ’s the problem ?
VHRED |  I don’t know what you want to do . if you want to do it , you need to do it to do it in the terminal ?
hredGAN_w |  you don ’ t have to do anything , just type in the terminal and it should be to find the right device
hredGAN_u |  you can have a look at the output of the command . . .
Context_1 |  good deal… cat /etc/X11/default-display-manager
HRED |  what ’s the problem ?
VHRED |  do you know what you want to do ?
hredGAN_w |  I ’ m trying to figure a command that I can find to find out the file that I can find in the file”
hredGAN_u |  I don ’ t see the point , but I ’ m not sure how to do that .
Context_2 |  /usr/sbin/lightdm http://paste.ubuntu.com/1286224/ $<$—- my /etc/X11/xorg.conf
HRED |  what ’s the problem ?
VHRED |  is there a way to do that in the terminal ?
hredGAN_w |  did you just type \” sudo mount -a \” ?
hredGAN_u |  i have no idea , i just installed ubuntu and i have no idea how to do that
Table 3:  Sample responses of HRED, VHRED and hredGAN.

Quantitative Generator Performance: We run autoregressive inference for all
the models (using optimum $\alpha$ values for hredGAN models and selecting the
best of $L=64$ responses using a discriminator) with dialogue contexts from a
unique test set. Also, we compute the average BLEU-2, ROUGE-2(f1),
Distinct(1/2), and normalized average sequence length (NASL) scores for each
model and summarize the results in the middle of Table 1. Distinct(1/2)
largely agrees with the perplexity score. Most scores, similar to the
perplexity, indicate that hredGAN models perform better than (V)HRED on both
datasets. However, on the UDC ROUGE and MTC BLEU, VHRED scores slightly better
than hredGAN_u but still worse than hredGAN_w.

A good dialogue model should find the right balance between precision (BLEU)
and diversity. We strongly believe that our adversarial approach is better
suited to solving this problem. As hredGAN generators explore diversity, the
discriminator ranking gives hredGAN an edge over (V)HRED because it helps
detect responses that are out of context and the natural language structure
(Table 2). Also, the ROGUE(f1) performance indicates that hredGAN_w strikes a
better balance between precision (BLEU) and diversity than the rest of the
models. This is also obvious from the quality of generated responses.

Qualitative Generator Performance: The results of the human evaluation are
reported in the last column of Table 1. The human evaluation agrees largely
with the automatic evaluation. hredGAN_w performs best on both datasets
although the gap is more on the MTC than on the UTC. This implies that the
improvement of HRED with adversarial generation is better than with
variational generation (VHRED). In addition, looking at the actual samples
from the generator outputs in Table 6 shows that hredGAN, especially
hredGAN_w, performs better than (V)HRED. While other models produce short and
generic utterances, hredGAN_w mostly yields informative responses. For
example, in the first dialogue in Table 6, when the speaker is sarcastic about
“the man upstairs”, hredGAN_w responds with the most coherent utterance with
respect to the dialogue history. We see similar behavior across other samples.
We also note that although hredGAN_u’s responses are the longest on Ubuntu (in
line with the NASL score), the responses are less informative compared to
hredGAN_w resulting in a lower human evaluation score. We reckon this might be
due to a mismatch between utterance-level noise and word-level discrimination
or lack of capacity to capture the data distribution using single noise
distribution. We hope to investigate this further in the future.

Discriminator Performance: Although only hredGAN uses a discriminator, the
observed discriminator behavior is interesting. We observe that the
discriminator score is generally reasonable with longer, more informative and
more persona-related responses receiving higher scores as shown in Table 2. It
worth to note that this behavior, although similar to the behavior of a human
judge is learned without supervision. Moreover, the discriminator seems to
have learned to assign an average score to more frequent or generic responses
such as “I don’t know,” “I’m not sure,” and so on, and high score to rarer
answers. That’s why we sample a modified noise distribution during inference
so that the generator can produce rarer utterances that will be scored high by
the discriminator.

##  6 Conclusion and Future Work

In this paper, we have introduced an adversarial learning approach that
addresses response diversity and control of generator outputs, using an HRED-
derived generator and discriminator. The proposed system outperforms existing
state-of-the-art (V)HRED models for generating responses in multi-turn
dialogue with respect to automatic and human evaluations. The performance
improvement of the adversarial generation (hredGAN) over the variational
generation (VHRED) comes from the combination of adversarial training and
inference which helps to address the lack of diversity and contextual
relevance in maximum likelihood based generative dialogue models. Our analysis
also concludes that the word-level noise injection seems to perform better in
general.

## References

  * Bahdanau et al. (2015) D. Bahdanau, K. Cho, and Y. Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  In _Proceedings of International Conference of Learning Representation (ICLR 2015)_.
  * Banchs (2012) R. E. Banchs. 2012.  Movie-dic: A movie dialogue corpus for research and development.  In _Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics_ , pages 203––207.
  * Bruni and Fernández (2018) E. Bruni and R. Fernández. 2018.  Adversarial evaluation for open-domain dialogue generation.  In _Proceedings of the 18th Annual SIGdial Meeting_.
  * Che et al. (2017) T. Che, Y. Li, R. Zhang, R. D. Hjelm, W. Li, Y. Song, and Y. Bengio. 2017.  Maximum-likelihood augmented discrete generative adversarial networks.  In _arXiv preprint arXiv:1702.07983_.
  * Cho et al. (2014) K. Cho, B. Merrienboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio. 2014.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  In _Proceedings of International Conference of Learning Representation (ICLR 2015)_ , pages 1724––1734.
  * Glorot and Bengio (2010) X. Glorot and Y. Bengio. 2010.  Understanding the difficulty of training deep feedforward neural networks.  In _International conference on artificial intelligence and statistics_.
  * Goodfellow et al. (2014) I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. 2014.  Generative adversarial nets.  In _Proceedings of Advances in Neural Information Processing Systems (NIPS 2014)_.
  * Isola et al. (2017) P. Isola, J. Y. Zhu, T. Zhou, and A. A. Efros. 2017.  Image-to-image translation with conditional adversarial networks.  In _Conference on Computer Vision and Pattern Recognition (CVPR, 2017)_.
  * Jean et al. (2015) S. Jean, K. Cho, R. Memisevic, and Y. Bengio. 2015.  On using very large target vocabulary for neural machine translation.  In _arXiv preprint arXiv:1412.2007_.
  * Kannan and Vinyals (2017) A. Kannan and O. Vinyals. 2017.  Adversarial evaluation of dialogue models.  In _arXiv preprint arXiv:1701.08198v1_.
  * Lamb et al. (2016) A. Lamb, A. Goyah, Y. Zhang, S. Zhang, A. Courville, and Y. Bengio. 2016.  Professor forcing: A new algorithm for training recurrent networks.  In _Proceedings of Advances in Neural Information Processing Systems (NIPS 2016)_.
  * Li et al. (2016a) J. Li, M. Galley, C. Brockett, J. Gao, and B. Dolan. 2016a.  A diversity-promoting objective function for neural conversation models.  In _Proceedings of NAACL-HLT_.
  * Li et al. (2016b) J. Li, W. Monroe, A. Ritter, M. Galley, J. Gao, and D. Jurafsky. 2016b.  Deep reinforcement learning for dialogue generation.  In _arXiv preprint arXiv:arXiv:arXiv:1606.01541v4_.
  * Li et al. (2017) J. Li, W. Monroe, T. Shi, A. Ritter, and D. Jurafsky. 2017.  Adversarial learning for neural dialogue generation.  In _arXiv preprint arXiv:1701.06547_.
  * Lin (2014) C. Y. Lin. 2014.  Rouge: a package for automatic evaluation of summaries.  In _Proceedings of the Workshop on Text Summarization Branches Out_.
  * Liu et al. (2016) C. Liu, R. Lowe, I. V. Serban, M. Noseworthy, L. Charlin, and J. Pineau. 2016.  How not to evaluate your dialogue system: An empirical study of unsupervised evaluation metrics for dialogue response generation.  In _Proceedings of EMNLP_ , pages 2122–2132.
  * Luong et al. (2015) M. T. Luong, I. Sutskever, Q. V. Le, O. Vinyals, and W. Zaremba. 2015.  Addressing the rare word problem in neural machine translation.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics_.
  * Papineni et al. (2002) K. Papineni, S. Roukos, T. Ward, and W. Zhu. 2002.  Bleu: A method for automatic evalution of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311––318.
  * Serban et al. (2016) I. Serban, A. Sordoni, Y. Bengio, A. Courville, and J. Pineau. 2016.  Building end-to-end dialogue systems using generative hierarchical neural network models.  In _Proceedings of The Thirtieth AAAI Conference on Artificial Intelligence (AAAI 2016)_ , pages 3776–3784.
  * Serban et al. (2017a) I. V. Serban, T. Klinger, G. Tesauro, K. Talamadupula, B. Zhou, Y. Bengio, and A. Courville. 2017a.  Multiresolution recurrent neural networks: An application to dialogue response generation.  In _Proceedings of The Thirty-first AAAI Conference on Artificial Intelligence (AAAI 2017)_.
  * Serban et al. (2017b) I. V. Serban, A. Sordoni, R. Lowe, L. Charlin, J. Pineau, A. Courville, and Y. Bengio. 2017b.  A hierarchical latent variable encoder-decoder model for generating dialogue.  In _Proceedings of The Thirty-first AAAI Conference on Artificial Intelligence (AAAI 2017)_.
  * Sutskever et al. (2014) I. Sutskever, O. Vinyals, and Q. Le. 2014.  Sequence to sequence learning with neural networks.  In _Proceedings of Advances in Neural Information Processing Systems (NIPS)_ , pages 3104––3112.
  * Vinyals and Le (2015) O. Vinyals and Q. Le. 2015.  A neural conversational model.  In _Proceedings of ICML Deep Learning Workshop_.
  * Williams and Zipser (1989) R. J. Williams and D. Zipser. 1989.  A learning algorithm for continually running fully recurrent neural networks.  _Neural computation_ , 1(2):270––280.
  * Xing et al. (2017) C. Xing, W. Wu, Y. Wu, M. Zhou, Y. Huang, and W. Ma. 2017.  Hierarchical recurrent attention network for response generation.  In _arXiv preprint arXiv:1701.07149_.
  * Xu et al. (2017) Z. Xu, B. Liu, B. Wang, S. Chengjie, X. Wang, Z. Wang, and C. Qi. 2017.  Neural response generation via gan with an approximate embedding layer.  In _EMNLP_.
  * Yu et al. (2017) L. Yu, W. Zhang, J. Wang, and Y. Yu. 2017.  Seqgan: sequence generative adversarial nets with policy gradient.  In _Proceedings of The Thirty-first AAAI Conference on Artificial Intelligence (AAAI 2017)_.
  * Zhang et al. (2018) Y. Zhang, M. Galley, J. Gao, Z. Gan, X. Li, C. Brockett, and B. Dolan. 2018.  Generating informative and diverse conversational responses via adversarial information maximization.  In _arXiv preprint arXiv:arXiv:1809.05972v5_.
  * Zhang et al. (2017) Y. Zhang, Z. Gan, K. Fan, Z. Chen, R. Henao, D. Shen, and L. Carin. 2017.  Adversarial feature matching for text generation.  In _arXiv preprint arXiv:1706.03850_.

Model | Teacher Forcing | Autoregression
---|---|---
Perplexity | BLEU-2 | ROUGE-2 | DISTINCT-1/2 | NASL
MTC |  |  |  |  |
HRED | 31.92/36.00 | 0.0474 | 0.0384 | 0.0026/0.0056 | 0.535
HRED+Attn | 18.70/19.02 | 0.0425 | 0.2239 | 0.0397/0.1567 | 0.527
hredGAN_no_noise | 18.93/19.19 | 0.0355 | 0.1839 | 0.0272/0.0978 | 0.471
UDC |  |  |  |  |
HRED | 69.39/86.40 | 0.0177 | 0.0483 | 0.0203/0.0466 | 0.892
HRED+Attn | 43.43/43.92 | 0.0140 | 0.0720 | 0.0473/0.1262 | 0.760
hredGAN_no_noise | 43.48/44.04 | 0.0123 | 0.0827 | 0.0398/0.1147 | 0.908
Table 4: Generator Performance: HRED, HRED+Attn and hredGAN without noise

##  Appendix A Ablation Experiments

Before proposing the above adversarial learning framework for multi-turn
dialogue, we carried out some experiments.

###  A.1 Generator:

We consider two main factors here, i.e., addition of an attention memory and
injection of Gaussian noise into the generator input.

####  A.1.1 Addition of Attention Memory

First, we noted that by adding an additional attention memory to the HRED
generator, we improved the test set perplexity score by more than 12 and 25
points on the MTC and UDC respectively as shown in Table 4. The addition of
attention also shows strong performance at autoregressive inference across
multiple metrics as well as an observed improvement in response quality. Hence
the decision for the modified HRED generator.

####  A.1.2 Injection of Noise

Before injecting noise into the generator, we first train hredGAN without
noise. The result is also reported in 4. We observe accelerated generator
training but without an appreciable improvement in performance. It seems the
discrimination task is very easy since there is no stochasticity in the
generator output. Therefore, the adversarial feedback does not meaningfully
impact the generator weight update.

Finally, we also notice that even with noise injection, there is no
appreciable improvement in the auto-regressive performance if we sample with
$L=1$ even though the perplexity is higher. However, as we increase $L$,
producing $L$ responses per turn, the discriminator’s adversarial selection
gives a better performance as reported in Table 1.

Therefore, we conclude that the combination of adversarial training and
adversarial inference helps to address the lack of diversity and contextual
relevance observed in the generated responses.

###  A.2 Discriminator:

Before deciding on the word-level discrimination, we experimented with
utterance-level discrimination. The utterance-level discriminator trains very
quickly but it leads to mostly generic responses from the generator. We also
note that utterance-level discriminator scores are mostly extreme (i.e.,
either low or high). Since we had used a convolutional neural network
discriminator (Yu et al., 2017) in our experiments, we hope to investigate
this further with other architectures.

###  A.3 Adversarial Training:

Lastly, we also tried a basic policy gradient approach (Li et al., 2017),
where word-level discriminator score is used as a reward for each generated
word token, but this leads to training instability. This is probably due to
the instability of Monte Carlo sampling over a large vocabulary size. We
believe this might improve with other sampling methods such as importance
sampling and hope to investigate this further in the future.

Model |  Response
---|---
Context_0 |  $<$person$>$ i ’ ve raised my rate . i might even cut my sessions to forty minutes .
HRED |  i ’ m sorry , $<$person$>$ .
VHRED |  $<$person$>$, $<$person$>$, $<$person$>$, $<$person$>$ .
hredGAN_w |  $<$person$>$ , i ’ m sorry , but i ’ m not sure if you ’ re really a very good guy .
hredGAN_u |  i ’ ll never see them again , $<$person$>$ .
Context_0 |  i ’ m going to handle this exactly the way your father would have handled this . i ’ ve got it solved .
Context_1 |  you ’ ve got it solved ? where is she ?
HRED |  i don ’ t know .
VHRED |  $<$person$>$, , i ’ m sorry.
hredGAN_w |  to the end of a beautiful woman who will be very happy .
hredGAN_u |  i ’ m sorry , i just didn ’ t know –
Context_0 |  of course not ! ¡person¿ ’ s like a daughter to me . her father and i taught at university together . a good man , but he never listened .
HRED |  i ’ m sorry , $<$person$>$.
VHRED |  $<$person$>$, mr . $<$person$>$ .
hredGAN_w |  $<$person$>$ , i know it ’ s been all six years since i told him about you .
hredGAN_u |  i ’ m sure you didn ’ t , but i would have done a little more .
Context_0 |  of course not ! ¡person¿ ’ s like a daughter to me . her father and i taught at university together . a good man , but he never listened .
Context_1 |  neither did i .
HRED |  i ’ m sorry , $<$person$>$.
VHRED |  $<$person$>$ , you ’ re a $<$unk$>$ .
hredGAN_w |  $<$person$>$, i know you ’ re think about it . think it ’ ll be time , right ?
hredGAN_u |  i ’ ll be the first one . if it did you , you ’ ll be it .
Context_0 |  come on , $<$person$>$ , we could have a great week up in vermont .
Context_1 |  i see what you mean . but wednesday we ’ ve got to be back in new york .
HRED |  $<$person$>$ .
VHRED |  $<$person$>$ , i don ’ t know what you ’ re going to do .
hredGAN_w |  $<$person$>$ , i know . i ’ m kind of busy here .
hredGAN_u |  i ’ m sorry , i can ’ t .
Context_0 |  isabel ?
Context_1 |  hi .
HRED |  that ’ s what i ’ m talking about .
VHRED: |  you ’ re not going to be a $<$unk$>$ , $<$person$>$ .
hredGAN_w |  $<$person$>$ ?
hredGAN_u |  what do you want to know ?
Context_0 |  you understand mr . $<$person$>$ is constantly barraged with nuisance litigation and irs audits .
Context_1 |  of course .
HRED |  that ’ s right , $<$person$>$ .
VHRED: |  $<$person$>$ , you ’ re going to be a $<$unk$>$ of the $<$unk$>$ .
hredGAN_w |  $<$person$>$ , i ’ m sure , but you ’ re probably still in to the new $<$person$>$ ’ s house , huh ?
hredGAN_u |  you ’ re gon na be a little boy , and i ’ m not gon na get out !
Context_0 |  $<$person$>$ ’ t go into my room , she ’ s asleep .
Context_1 |  $<$person$>$ , but the nanny , mrs . $<$person$>$ , she wants to see her .
HRED |  i ’ m sorry , $<$person$>$ .
VHRED: |  $<$person$>$ , mr . $<$person$>$ .
hredGAN_w |  $<$person$>$ , i know . but she ’ s never seen me anyway .
hredGAN_u |  i ’ m sorry i didn ’ t know what to say .
Context_0 |  what was that for ?
Context_1 |  i ’ d forgotten how exciting it is working together .
HRED |  i ’ m sorry , $<$person$>$ .
VHRED: |  $<$person$>$ , $<$person$>$ . i don ’ t know .
hredGAN_w |  i ’ m sorry , $<$person$>$ . so many people are so interested , but you ’ re a very nice guy .
hredGAN_u |  i ’ ve always been so sure to $<$person$>$ .
Context_0 |  a teacher ’ s .
Context_1 |  oh my god .
HRED |  i ’ m sorry , $<$person$>$ .
VHRED: |  $<$person$>$ , $<$person$>$ ’ t worry about it . i don ’ t know what you ’ re doing .
hredGAN_w |  i ’ m sorry . i didn ’ t mean to . i didn ’ t mean to hurt you . i just wanted you
hredGAN_u |  $<$person$>$ , i don ’ t want to be your friend .
Context_0 |  i took the initiative .
Context_1 |  you haven ’ t been given an assignment in this case .
HRED |  $<$person$>$ .
VHRED: |  $<$person$>$ , $<$person$>$ , $<$person$>$ , $<$person$>$ . i ’ m not going to get out of the $<$unk$>$ .
hredGAN_w |  i ’ m not sure . $<$continued_utterance$>$ i ’ m not gon na do you this shit anyway , $<$person$>$ .
hredGAN_u |  $<$person$>$ , i guess i didn ’ t .
Table 5: Additional sample responses of HRED, VHRED and hredGAN on Movie.

Model |  Response
---|---
Context_0 |  what’s the command you are running to chroot and the error message you get in return?
Context_1 |  i mountded the device sudo mount /dev/sda1 /mnt - that works - then sudo chroot /mnt – error is no such file or command
HRED |  what ’s the problem ?
VHRED |  is there a way to do that ? what do you mean ?
hredGAN_w |  I have no idea , I just did a sudo fdisk and it said it was mounted
hredGAN_u |  I ’ m trying to get the latest version of ubuntu , but I ’ m getting a lot of problems .
Context_0 |  Hmm, have you checked that ICMP is being allowed all the way through and that the server responds to other ICMP requests?
Context_1 |  now i can ping it (i had to enable the lzo compression on client) i cannot reach the remote subnet adding a rule in the firewall forward the lan to vpn
HRED |  what ’s the problem ?
VHRED |  I don’t know what you want to do
hredGAN_w |  I have no idea , I ’ m just trying to get the ip address from the router to the router”
hredGAN_u |  I ’ m not sure if that ’ s the case , but I ’ m not sure if it ’ s a good idea to have a look at the output .
Context_0 |  The netboot one is suppose to download packages from the net.
HRED |  I don’t know what you want to do .
VHRED |  how do I do that ?
hredGAN_w |  I ’ m not sure of a command to do so I can just install the ubuntu . iso and burn a new iso
hredGAN_u |  you can ’ t have a look at the man page . . .
Context_0 |  The netboot one is suppose to download packages from the net.
Context_1 |  like the ones to be installed? or the installed to be run?
HRED |  I don’t know what the problem is .
VHRED |  is there a way to install the package manager ?
hredGAN_w |  you don ’ t need to install the whole system , just install the ubuntu installer
hredGAN_u |  I ’ m trying to install a _UNK version of ubuntu , but I ’ m trying to install it on my laptop .
Context_0 |  You trying to mount it open with the password?
HRED |  I have to do that , but I have a problem with the same problem .
VHRED |  is there a way to do ?
hredGAN_w |  yes , I ’ m not sure if it ’ s mounted or not
hredGAN_u |  I ’ m trying to install the latest version of Ubuntu , but I ’ m running on a _UNK .
Context_0 |  are you using lvm for your root partition?
HRED |  yes , but I have a problem with a new user , but I don’t want to do that .
VHRED |  what is the best way to do that ? what is that ?
hredGAN_w |  yes , I ’ m on a live system , I ’ m trying to use the partition to boot from windows
hredGAN_u |  I ’ m not sure if it ’ s a good idea to have a backup of the system . . .
Context_0 |  are you using lvm for your root partition?
Context_1 |  i have the same config working on a 10.04 box. It appears in 12.04 lvm is on upstart and multipath is not. i do use lvm for my root folder nifty, is there any way to work around it? have you heard of anyone posting a bug about this to have it looked at? darn…. well i hope they can fix this eventually i hope they keep initrd around and move everything to upstart. Upstart is not easy to setup for programs that don’t come packaged for upstart.
HRED |  I don’t know what the problem is , but I don’t know what the problem is . ?
VHRED |  is there a way to do that ? or **unknown** ?
hredGAN_w |  you can also try the live cd and see if you can get it back up the live”
hredGAN_u |  I ’ m trying to get my wireless working on my laptop , but I ’ m getting to the point that I can be able to use the wireless card to get the wireless working .
Context_0 |  are you using lvm for your root partition?
Context_1 |  i have the same config working on a 10.04 box. It appears in 12.04 lvm is on upstart and multipath is not. i do use lvm for my root folder nifty, is there any way to work around it? have you heard of anyone posting a bug about this to have it looked at? darn…. well i hope they can fix this eventually i hope they keep initrd around and move everything to upstart. Upstart is not easy to setup for programs that don’t come packaged for upstart.
Context_2 |  yes, because i cant supply it at boot time, i want the truecrypt drive to come up by itself without manual intervention
HRED |  what is the problem ?
VHRED |  what do you mean ?
hredGAN_w |  you can also mount a new one and put the mount command to the mount point”
hredGAN_u |  I ’ m trying to get my sound working , but I ’ m trying to get my sound working .
Table 6: Additional sample responses of HRED, VHRED and hredGAN on Ubuntu.