# Controllable Path of Destruction

Matthew Siper  Game Innovation Lab
New York University
New York, USA
<EMAIL_ADDRESS>Sam Earle  Game Innovation Lab
New York University
New York, USA
<EMAIL_ADDRESS>Zehua Jiang  Game Innovation Lab
New York University
New York, USA
<EMAIL_ADDRESS>Ahmed Khalifa  Institute of Digital Games
University of Malta
Msida, Malta
<EMAIL_ADDRESS>Julian Togelius  Game Innovation Lab
New York University
New York, USA
<EMAIL_ADDRESS>
###### Abstract

Path of Destruction (PoD) is a self-supervised method for learning iterative
generators. The core idea is to produce a training set by destroying a set of
artifacts, and for each destructive step create a training instance based on
the corresponding repair action. A generator trained on this dataset can then
generate new artifacts by repairing from arbitrary states. The PoD method is
very data-efficient in terms of original training examples and well-suited to
functional artifacts composed of categorical data, such as game levels and
discrete 3D structures. In this paper, we extend the Path of Destruction
method to allow designer control over aspects of the generated artifacts.
Controllability is introduced by adding conditional inputs to the state-action
pairs that make up the repair trajectories. We test the controllable PoD
method in a 2D dungeon setting, as well as in the domain of small 3D Lego
cars.

###### Index Terms:

Procedural Content Generation, Supervised Learning, Repair Function,
Controllability, Data Augmentation

##  I Introduction

Self-supervised learning in various guises has enabled dramatic advances in
generative AI over the last decade. Generative Adversarial Networks [1] and
diffusion models [2] have enabled the creation of high-quality images in a
variety of styles, and transformers underlie large language models [3] which
are poised to impact any field of human activity which involves text
processing. These deep learning architectures are generally tied to particular
representation formats: in particular, transformers operate on sequences of
tokens and GANs and diffusion models work with matrices of real numbers which
are interpreted as RGB values. But what these methods are above all is data-
hungry. A GAN or diffusion model is trained on at least thousands, often
millions, of images [4], and LLMs are typically trained on terabytes of text
[5].

This leaves a large space of creative domains which are not naturally
expressed as matrices of real numbers or sequences of tokens underserved by
current self-supervised learning methods. Even more importantly, for most
domains comparatively little data is available to train on, rendering existing
self-supervised methods largely ineffective.

Path of Destruction is a recently developed self-supervised method for
learning generators of structured content. The method is very data-effective.
Although it was developed separately from diffusion models, it has conceptual
similarities. The basic idea is to iteratively destroy the target content, one
small change at a time, and create a dataset of the changes. In the generated
dataset, each instance has part of the destroyed state as an input and the
associated repair action (reverse of the destruction action) as the target. By
rolling out multiple paths of destruction, an arbitrarily large set of repair
actions can be created even when starting with a small initial set of
artifacts. Standard supervised learning can then be used to train a generator
that generates novel artifacts by “repairing” from random starting states.

Figure 1: System diagram of the path of destruction data generation loop
including the new condition signal.

The original Path of Destruction method [6] could generate novel, playable
levels for several 2D games based on training on as little as 5 source levels,
although performance improved with more levels to train on. However, that
algorithm provided no way for the user to influence the design of the
generated content beyond curating the training set. In this paper, we describe
and evaluate a new version of the Path of Destruction algorithm which allows a
user to control aspects of the output. This opens up new avenues for using
Path of Destruction as a design tool in interactive applications [7].

The basic idea of Controllable Path of Destruction is to include conditional
inputs in the generator. These conditional inputs are also part of the
training data that is generated by destroying the artifact and are based on
the properties of the artifact that was originally destroyed in the process.
For example, if the controllable aspect of the generator is the number of
tiles of type X, then the dataset will contain a conditional input for the
corresponding tile count. All instances deriving from the destruction of a
particular artifact will have the tile count from that artifact.

To improve the performance of our algorithm, in particular, for settings with
limited training data, we propose signed inputs, where the conditional input
is not the absolute value of a feature, but whether the artifact that is being
generated is currently above or below the target value. Using signed inputs
(positive, negative, zero) helps to have a bigger distribution over these
different conditions compared to using direct values. We hypothesize that this
helps the network to learn the meaning of these conditions better than using
actual values.

We test our algorithm in two domains: 2D “Zelda” levels (single-room levels
for a much-simplified version of the dungeon system of The Legend of Zelda
(Nintendo, 1986)) and small 3D Lego cars.

##  II Related work

The Path of Destruction method is conceptually and functionally related to
several other methods originating from different communities. One of these
closely related methods is WaveFunctionCollapse (WFC), a method that has
origins in the graphics community but was popularized by Maxim Gumin [8].
While WFC is used for PCG in some games, in particular indie games [9], it can
also be seen as a form of constraint satisfaction and related to constraint
satisfaction research in the AI community [10]. WFC operates on (preferably
low-dimensional) pixel- or tile-based 2D artifacts and learns to generate new
artifacts in the same style. It does this by learning the local rules that
relate the pixels/tiles in the input artifact, and ensuring that the generated
artifact adheres to the same rule. Every patch in the generated artifact must
have occurred somewhere in the input. Like WFC, Path of Destruction [6]
largely learns local rules and is highly data-efficient, but uses a deep
neural network and tries also to learn global rules as the training data is
generated towards certain targets.

Another highly influential family of methods with conceptual similarities to
Path of Destruction is diffusion models111Path of Destruction was developed
independently of diffusion models, and the relation was pointed out to the
authors of the first Path of Destruction paper after it had been posted on
ArXiv [11, 2]. Diffusion models are typically trained on large sets of images
[4]. On each image, noise is iteratively applied until only noise remains. The
model is then iteratively trained to regenerate the original image from the
noisy version of the image. The Path of Destruction is conceptually similar in
that it also teaches neural networks to recreate artifacts after destroying
them. However, whereas diffusion models operate in parallel (on the whole
image at a time) and with continuous-valued pixels, Path of Destruction
operates sequentially, changing one pixel/tile/element at a time. The current
implementation operates on discrete, categorical tile values which also
differentiates it from diffusion models. Given a sufficiently wide definition
of “diffusion models”, one might indeed choose to see Path of Destruction as a
type of diffusion model; we have no strong opinion on this matter. However, we
note that the data efficiency of Path of Destruction is much better than any
diffusion model we know of, in the sense that it can learn to generate good
artifacts with very few training examples. We also point out that PoD was able
to learn functional relations between tiles that enabled it to generate
playable levels which is not the case for diffusion models.

A third method that should be mentioned in this context is procedural content
generation via reinforcement learning, or PCGRL for short [12]. In PCGRL,
reinforcement learning algorithms are used to train neural nets to construct
levels. Path of Destruction shares its scanline-like mode of operation with
the “narrow” variety of PCGRL, and the controllable version of Path of
Destruction presented here is inspired by Controllable PCGRL [13]. As
discussed later, the very same network could plausibly be trained by either
method, suggesting interesting combinations of these methods. However, unlike
PCGRL where a reward function is used to train the generator network, Path of
Destruction is a self-supervised method trained on existing artifacts.

In this paper, we apply Controllable Path of Destruction to game-level
generation, a problem that has been widely studied within procedural content
generation (PCG) research [14]. Typically, PCG is motivated by giving game
developers new tools, but procedurally generated levels are also important for
open-ended learning [15]. In recent years, machine learning techniques have
increasingly been applied to PCG, including self-supervised methods [16, 17,
18].

Figure 2: System diagram of the inference step using the trained model from
the path of destruction. The difference between this figure and the normal
path of destruction is the condition signal.

(a) Zelda

(b) Lego Car

Figure 3: Examples from the goal set for both domains.

##  III Controllable Path of Destruction

Path of Destruction is a data augmentation method introduced by Siper et al.
[6] that helps to create a big training dataset given a small number of
training data. The method is similar to diffusion models [2] but it can work
with discrete data and doesn’t have any conditions on the training noise.
Furthermore, Path of Destruction can work using a very small amount of data.
To avoid confusion, the input data that is used to create the training data is
called the goal set, while the output of the technique is called the training
set.

The original Path of Destruction follows the following steps to create the
training set:

  1. 1.

Pick a random level/object from the goal set and set the current state
($Level_{t}$) equal to it.

  2. 2.

Pick a random location on the current state.

  3. 3.

Change the current state with a randomly selected value ($DestroyAction_{t}$).

  4. 4.

Record the value of the current location before the change
($RepairAction_{t}$) and the new state ($Level_{t+1}$) as a state-action pair
to save it in the training set.

  5. 5.

If the new state doesn’t follow a certain noise distribution called Starting
set, Go back to step 2.

  6. 6.

Repeat the above steps until we have a big enough number of state action
pairs.

After the training set is generated, we train a neural network using
supervised learning to learn how to reverse the destruction. After the
training is done, the network can be used to generate new content by following
the following steps:

  1. 1.

Generate a random state ($StartLevel$) that follows the same distribution of
the starting set and set it as the current state ($Level_{t}$).

  2. 2.

Pick a random location of the state and apply the network using the current
state ($Level_{t}$).

  3. 3.

Replace the location value with the output from the network
($RepairAction_{t}$) to get the new state ($Level_{t+1}$).

  4. 4.

Repeat the above steps until the object reaches a certain minimum quality (for
game levels until the level is playable) or time is up.

One of the main issues of this method is that it is not easy to control any of
the features of the generated content. The only way of control is through the
starting state which doesn’t give much understanding about the final generated
content. To battle this problem, we took inspiration from Earle et al.’s work
[13] and decided to explore the idea of having a control signal that can
influence the algorithm toward generating content with specific features. For
example, if we are generating a level for Super Mario Bros (Nintendo, 1985),
there could be an input signal that controls how many jumps the player needs
to do to beat the level. Figure 1 and 2 show the changes to the flow explained
above. The big difference is during generating the data set we need to make
sure to record the target condition value ($Condition_{t}$) at step 4 as part
of the training data. For the inference side, the user needs to pick the
target condition ($Condition_{t}$) when generating the starting state at step
1.

Originally these input signals were absolute target values of what is
required. For example, if we want to have 5 enemies, we need to give that
value to the model. The problem was there is few goal states which made the
number of conditions limited and doesn’t cover the whole space of conditions.
For example, if we have 5 goal levels, we only have 5 different conditions and
some of them might be repeated. In early experiments, the learned model was
not able to generalize and understand other values outside the ones that it
was trained on. We decided to use the same idea from Earle et al. work [13]
where instead of using the target values, we use a signed relative signal that
tells the system if it should increase (1), decrease (-1), or keep (0) that
target value. For example, if we are trying to generate a level with 5
enemies, we first check the current level number of enemies if there are 8
enemies then the signal is -1.

We updated the main algorithm to incorporate this new condition signal. For
the data generation process, we now calculate the signal sign by calculating
the current value of the condition and comparing it with the goal state value
and then get added as part of the input state in the training data. The
training data now is observation ($Level_{t}$), condition signal
($Condition_{t}$), and output ($RepairAction_{t}$) where both the observation
and condition signal are the input for the machine learning model. For the
generation phase, we need to calculate at every step the value of the
condition with respect to the user target value. For example, if the user
wants a level with 20 enemies and the current state has 40, then the condition
is equal to -1.

Using the signed relative signal helps the network to learn a more generic
meaning of the signal than targets as we have more examples for it. In the
future, we could use a more intelligent way of destruction that make sure that
all the different conditions are well covered. As in the current method, some
conditions might be harder to cover. For example, imagine one of the
conditions is the longest path in a maze, most of the destruction will be
decreasing that path which makes the condition always 1 in most of the
training data. This problem becomes more apparent when there the number of
conditions is increased where certain combinations might rarely appear during
random destruction.

##  IV Experiments

To analyze and study this controllable model, we decided to test the model on
two domains (figure 3):

  * •

Zelda Level Generation: is a 2D top-down demake of the dungeon system of The
Legend of Zelda (Nintendo, 1986). The goal of the game is to get a key and
reach the door while avoiding being killed by enemies. The player can kill
enemies using their swords. The goal is to create a playable level with one
key, one door, and one player.

  * •

Lego Car Generation: is a 3D framework using a constrained set of Lego pieces
to create a 3D car that is functional (has 4 wheels).

We picked these two domains as they show the diversity and the ability of the
method to work between a tile-based restrictive level to more free-form Lego
pieces.

Figure 4: The network architecture used as the generation model.

For both problems, we used a simple architecture (figure 4) similar to the
Deep Q-Learning architecture [19]. The architecture consists of 3 convolution
layers followed by two fully connected layers. All the intermediate layers are
using a Relu activation function, while the final layer is using a Softmax
layer. We also added a MaxPooling layer after the first layer to reduce the
size of the input state. The network takes two inputs: the current observation
($Level_{t}$) and the current condition signal ($Condition_{t}$). Both
observation and condition signal is encoded as one-hot encoding as they are
discrete values. The current observation goes through the convolution layers
and gets concatenated to the condition signal for the last two layers. The
difference between the architecture of Lego and Zelda problems is that in Lego
the convolution and max pooling layers are 3D instead of 2D.

###  IV-A Zelda Level Generation

For this problem, we cared about 3 different controllable parameters:

  * •

Number of Enemies: The number of enemies in the generated level.

  * •

Distance to Nearest Enemy: The Manhattan distance to the nearest enemy in the
generated level.

  * •

Solution Length: The number of player steps that are needed to solve the
current level (The Manhattan distance between the player to the key added to
the Manhattan distance from the key to the door).

We picked these parameters as they control the target experience of the game.
For example, having a higher number of enemies will make the game harder and
has more action moments while having closer enemies makes the game more
intense and reactive when you start. Finally, the solution length controls how
long should the game takes to solve and also control if the player passes
through multiple enemies.

For this experiment, we used full observation instead of partial observation
which was used before [6]. The reason for that is we wanted the network to
have the ability to learn easily about these conditions. The observation size
is 19x19 where the extra outside areas were padded using solid tiles. The
starting set distribution follows the distribution of Zelda’s goal-set levels.
We used 50 goal levels (figure 3(a)) to generate 962,500 training data. We
train three different networks for 250 epochs with a batch size of 256 using
Adam optimizer with default settings.

For the generation process, we sampled a random level from the distribution
and run the model sequentially on all the locations for 105 steps or until we
find a playable level within a threshold for the condition target. A level is
playable if it is fully connected with one key, door, and player. Table I
shows the range of the conditional values and the different conditional
thresholds that were used in the generation process. All the values were
picked relative to the training data. We generated 500 levels using the
network with condition values covering the space of different target values.

(a) Zelda levels generated by prompting the model for high/low path length.

(b) Zelda levels generated by prompting the model for high/low distance
between the player and the nearest enemy.

Figure 5: Generated Zelda levels using one of the trained neural networks. Condition | Min Value | Max Value | Threshold
---|---|---|---
Number of Enemies | 0 | 5 | 4
Distance to Nearest Enemy | 0 | 12 | 5
Solution Length | 10 | 31 | 6
TABLE I: The conditions values parameters used for the Zelda level generation.

###  IV-B Lego Car Generation

For the Lego car generation, we use the number of blocks as the control
parameter. This parameter is simple but it is the most useful one when
creating Lego objects as this is a common real-world restriction. In this
experiment, we didn’t differentiate between the different block types. In the
future, we think it makes more sense if the control was distributed on the
different types of blocks so people can tell the system the different numbers
of blocks they have from each.

In this experiment, we use 37 different block types and an observation size of
$6\times 6\times 6$. Therefore, the state space has size $6\times 6\times
6\times 37$ since we one-hot encode the blocks. There is no restriction about
where blocks can and can’t go, however, we would like to restrict this in the
future to avoid floating and overlapping blocks in the output. The goal set of
Lego cars used to generate the training trajectories consists of 15 different
cars of varying numbers of component blocks (figure 3(b)). The training set
consists of 300,000 state-action pairs produced from continuously iteratively
destroying a goal car to a noisy state. We trained three networks for 40
epochs, with a batch size of 256. We used the Adam optimizer with default
parameters.

For inference, we generated 520 cars from random starting states where each
voxel in the state space is filled with a uniformly randomly sampled block
from the 37 possible block types. Each episode consisted of 54 steps. There is
no early stopping condition similar to the Zelda generation problem as it is
harder to define one for Lego. One might say to stop when there are 4 wheels,
the problem with that is the generation could early terminate as the generator
might start by placing the wheels first. For the condition parameter, it was
tested for values between 15 and 27 blocks. Moreover, to evaluate agent
performance during inference, we define two output states of varying success.
A “success” output is one which has four wheels and where the difference
between the number of blocks in the output and the target input is no greater
than 6. A “partial success” lacks the difference condition but still contains
four wheels (it should be noted that we count the existence of a hubcap
without a tire as a wheel).

##  V Results

###  V-A Zelda Level Generation

Figure 6: Controllability of Zelda levels. The model learns to effectively
control the distance between the player and the nearest enemy, and the path
length from player to key to door, but is unable to exert control over the
number of enemies in a level, likely because of a lack of levels with diverse
numbers of enemies in the training set.

Figure 6 shows the controllability of the Zelda agent across the 3 metrics
measured: number of enemies, nearest enemy, and path length. The metric with
the least amount of controllability was the number of enemies. We attributed
this to the fact that the number of enemies from the goal maps was highly
concentrated duplicate values. The range of the enemies was also small (from 0
to 7). We think that having a smart destructive agent that creates the dataset
could help solve this problem. By contrast, the nearest-enemy and path-length
metrics show effective controllability as is evident by their respective
curves trending up and to the right. Figure 5 shows some of the generated
Zelda levels where the generated level reached the target value for both path
length and distance to the nearest enemy.

To test the quality of the generated content, we had to analyze the generated
levels in terms of quality and diversity. The quality is simple, we just check
the number of playable generated levels. Our generated levels have $78.86\pm
4.95\%$ playable levels. On the other hand, diversity is a little bit more
complex as we need to calculate two values: Inter-diversity and Intra-
diversity. Inter-diversity is responsible for calculating how much of the
generated levels are different from the goal-set levels, while Intra-diversity
makes sure that the generated maps are different from each other. The
diversity calculation used is the same one from Siper et al. work [6] where we
consider two maps to be different if they are $10\%$ different from each other
in terms of Hamming Distance. For inter-diversity, the generated output maps
are compared to their most similar goal map counterparts. Generated levels
that are less than $10\%$ different than their nearest goal map are removed
(i.e. considered as duplicates). Our Zelda level generators produce $25.32\pm
2.3\%$ unique levels by this inter-diversity metric. Intra-diversity is
computed by comparing each generated map to the other most similar generated
map and removing those that are less than $10\%$ different. $35.40\pm 1.12\%$
of our generated Zelda levels are unique in terms of intra-diversity. Finally,
to compute the total diversity, we first compute the Inter-diversity followed
by the intra-diversity; that is, starting with the set of all generated
levels, we first remove duplicates w.r.t. goal levels, then remove duplicates
w.r.t. other generated levels. The final diversity score (i.e. the percentage
of overall unique generated levels) is $24.42\pm 1.93\%$. Overall, the agent
performs reasonably well via being able to produce $78.86\pm 4.95\%$ playable
maps while maintaining a diversity of almost $24.42\%$ and effective
controllability with respect to the path length and nearest enemy metrics.

Model | Playability | Duplicated levels
---|---|---
CESAGAN | 47.00% | 60.30%
PoD | 37.88% | 0.00%
Controllable PoD | 78.96% | 26.90%
TABLE II: The agent performance w.r.t. its ability to generate diverse and
playable maps.

Table II, we compare the playability and percentage of duplicated levels to
the CESAGAN model from [20] and the original Path of Destruction [6]. As is
evident CESAGAN achieves a modest advantage over our model but this comes at
the expense of generating mostly duplicate output. This is compared to
controllable PoD which produces mostly new and diverse maps while having the
added feature of being effectively controllable on both path length and
enemies metrics. On the other hand, the normal PoD was able to have a lot less
duplicate levels with almost the same playability levels but in return, it is
pretty hard to control the output of the network.

###  V-B Lego Car Generation

Figure 7: Ability of the agent to repair a noisy starting state to a Lego car.
Figure 8: Controllability of Lego cars. The model learns to control the number
of blocks it uses to build a car.

(a) step 0

(b) step 0

(c) step 17

(d) step 20

(e) step 29

(f) step 32

(g) step 54

(h) step 54

Figure 9: Inference episodes in which the agent repairs from a noisy starting
state to a Lego car.

For the Lego experiments, we were concerned with whether an agent could learn
(and how well) to repair noisy states to valid cars using a small dataset of
15 goal cars. Due to the recent creation of the “legopcg” framework,
appropriate benchmark models aren’t yet readily available. Therefore, we
decided to compare the agent’s capacity to repair and its controllability to
random counterparts. Figure 7 shows the average similarity of final states to
the next closest goal for a given target metric. The blue bar, which indicates
our agent shows that the agent is able to repair from noisy random states well
across all of the target inputs tests, achieving around 80% similarity to the
next closest goal, respectively. By contrast, the random agent in green hovers
between 10-20% similarity which is competitive with the similarity of a given
starting, indicating that the random agent makes no progress towards the goal.
We also tested the generated cars to see how many of them have four wheels.
This number was computed to be $23.91\%\pm 5.2$ over the 3 separate inference
runs. This shows that the network was able to understand that to constitute a
car requires the existence of 4 wheels.

Figure 8 shows the controllability of the agent compared to its random
counterpart. As is evident the red curve of the agent, while muted, is still
pointing up and to the right. This is noticeably different than the random
green curve which shows no directional trend up and to the right. We
attributed the weakness in the controllability curve (as evidenced by the
small domain) of our agent to the fact that we are not yet checking for a
termination condition and instead fix the number of steps per episode. This
problem can be solved either by having a neural network that can detect if the
output is a Lego car or by training the network to know when it doesn’t need
to change. The second solution requires having a smart destructor that makes
sure there is an equal distribution of all of the different condition
parameters, including no-change. Figure 9 shows the repair steps towards
generating two different cars that didn’t exist in the original dataset.
Midway through, the object starts resembling a car and the following steps
were just polishing, suggesting a termination condition would help us generate
some interesting cars.

##  VI Discussion

One of the reasons diffusion models are so popular is their capability for a
text-guided generation; this is how Stable Diffusion and Midjourney can give
us high-quality images of so many things if we can only put them in words. The
basic idea is to pass the prompt through a language model to get an embedding
(a vector of some length, e.g. 512) and use this embedding as a conditional
input in training and inference. In theory, the control scheme presented in
this paper should be extendable to text-guided generation, so that we could
ask the generator to generate a level or Lego creation according to any
description. The big problem here is that given the large space of natural
language prompts, having a large training set seems necessary, and this amount
of training data is not necessarily available for the domains where PoD works
best. However, this may be solvable by using a pre-training and fine-tuning
scheme. Another solution to this problem is to try to use a smart destructor
to generate different artifacts in the middle of destruction that can have
different descriptions. This process could be automated using evolutionary
algorithms and an image-to-language model such as CLIP [21].

While Path of Destruction and PCGRL differ greatly in what they are trained on
– existing content vs rewards – they share a joint generation mode and network
structure. This suggests that we could combine the two methods in various
ways. For example, we could use Path of Destruction to generate levels and use
PCGRL to repair or fix them in case they had errors. You could also imagine
pre-training with PCGRL, perhaps over multiple different games, and fine-
tuning with Path of Destruction, to make the best use of limited training
data. Another idea could be using Path of Destruction as curriculum learning
for PCGRL in the same manner as Justesen et al. work [22]. The PoD can be used
to generate a destroyed level with a small trajectory of destruction where it
is easy for PCGRL to repair it. When the PCGRL gets better at doing these
repairs, we can increase the trajectory length until it reaches the whole
level. This might sound the same as starting from complete noise and learning
using PCGRL but in some hard domains, where the reward signal is sparse, we
think this methodology will help overcome this problem.

##  VII Conclusion

We presented Controllable Path of Destruction, a new version of the Path of
Destruction algorithm, and applied it to the generation of 2D Zelda levels and
3D Lego cars. Whereas the original Path of Destruction produced valid games
conditioned only on noise (destroyed levels), this controllable version allows
the user to guide the level-generation process toward relevant high-level
features. This is achieved by annotating paths of random “destructive” edits
with the features of each partially destroyed level state. In both domains,
the controllable Path of Destruction was able to generate proper content and
maintain controllability with respect to most of the control parameters.

The Lego domain comprises the first application of Path of Destruction to 3D.
We showed that with a small dataset of only 15 goal cars, the agent was able
to learn to repair from a noisy starting state toward a goal, achieving an
average of 80% similarity to the closest goal car across all of the targets
tested. Furthermore, we showed progress toward making the agent’s
controllability effective even though we didn’t enforce any boundary
thresholds on the input metric. Both of these constitute low-hanging
opportunities that we believe should improve the controllability of self-
supervised level generators. A lot of the issues raised by the new algorithm
are due to the random destruction of the tiles. We hypothesize that using a
smart destructor would elevate this problem by making sure that all the
conditional input values are covered.

## References

  * [1] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial networks,” _Communications of the ACM_ , vol. 63, no. 11, pp. 139–144, 2020.
  * [2] J. Ho, A. Jain, and P. Abbeel, “Denoising diffusion probabilistic models,” _Advances in Neural Information Processing Systems_ , vol. 33, pp. 6840–6851, 2020.
  * [3] C. Wang, M. Li, and A. J. Smola, “Language models with transformers,” _arXiv preprint arXiv:1904.09408_ , 2019.
  * [4] A. Baio, “Exploring 12 million of the 2.3 billion images used to train stable diffusion’s image generator,” https://waxy.org/2022/08/exploring-12-million-of-the-images-used-to-train-stable-diffusions-image-generator/, 2022, accessed: May 26, 2023.
  * [5] OpenAI, “Gpt-4 technical report,” _arXiv_ , 2023.
  * [6] M. Siper, A. Khalifa, and J. Togelius, “Path of destruction: Learning an iterative level generator using a small dataset,” _arXiv preprint arXiv:2202.10184_ , 2022.
  * [7] G. N. Yannakakis, A. Liapis, and C. Alexopoulos, “Mixed-initiative co-creativity,” in _Foundation of Digital Games_. ACM, 2014.
  * [8] M. Gumin, “Wave function collapse,” https://github.com/mxgmn/WaveFunctionCollapse, 2016, accessed: March 25, 2023.
  * [9] T. Thompson, “How townscaper works: A story four games in the making,” https://www.gamedeveloper.com/blogs/how-townscaper-works-a-story-four-games-in-the-making, 2022, accessed: May 26, 2023.
  * [10] I. Karth and A. M. Smith, “Wavefunctioncollapse is constraint solving in the wild,” in _Proceedings of the 12th International Conference on the Foundations of Digital Games_ , 2017, pp. 1–10.
  * [11] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli, “Deep unsupervised learning using nonequilibrium thermodynamics,” in _International Conference on Machine Learning_. PMLR, 2015, pp. 2256–2265.
  * [12] A. Khalifa, P. Bontrager, S. Earle, and J. Togelius, “Pcgrl: Procedural content generation via reinforcement learning,” in _Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment_ , vol. 16, no. 1, 2020, pp. 95–101.
  * [13] S. Earle, M. Edwards, A. Khalifa, P. Bontrager, and J. Togelius, “Learning controllable content generators,” in _2021 IEEE Conference on Games (CoG)_. IEEE, 2021, pp. 1–9.
  * [14] N. Shaker, J. Togelius, and M. J. Nelson, _Procedural content generation in games_. Springer, 2016.
  * [15] S. Risi and J. Togelius, “Increasing generality in machine learning through procedural content generation,” _Nature Machine Intelligence_ , vol. 2, no. 8, pp. 428–436, 2020.
  * [16] A. Summerville, S. Snodgrass, M. Guzdial, C. Holmgård, A. K. Hoover, A. Isaksen, A. Nealen, and J. Togelius, “Procedural content generation via machine learning (pcgml),” _IEEE Transactions on Games_ , vol. 10, no. 3, pp. 257–270, 2018.
  * [17] J. Liu, S. Snodgrass, A. Khalifa, S. Risi, G. N. Yannakakis, and J. Togelius, “Deep learning for procedural content generation,” _Neural Computing and Applications_ , vol. 33, no. 1, pp. 19–37, 2021.
  * [18] M. Guzdial, S. Snodgrass, and A. J. Summerville, _Procedural Content Generation Via Machine Learning: An Overview_. Springer, 2022.
  * [19] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” _arXiv preprint arXiv:1312.5602_ , 2013.
  * [20] R. R. Torrado, A. Khalifa, M. C. Green, N. Justesen, S. Risi, and J. Togelius, “Bootstrapping conditional gans for video game level generation,” in _Conference on Games_. IEEE, 2020, pp. 41–48.
  * [21] A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, G. Goh, S. Agarwal, G. Sastry, A. Askell, P. Mishkin, J. Clark _et al._ , “Learning transferable visual models from natural language supervision,” in _International conference on machine learning_. PMLR, 2021, pp. 8748–8763.
  * [22] N. Justesen, R. R. Torrado, P. Bontrager, A. Khalifa, J. Togelius, and S. Risi, “Illuminating generalization in deep reinforcement learning through procedural level generation,” _arXiv preprint arXiv:1806.10729_ , 2018.


# Collision-free Path Planning
in the Latent Space through cGANs

Tomoki Ando
Waseda Univ. & AIST, Japan
<EMAIL_ADDRESS>
&Hiroki Mori
Waseda Univ. & AIST, Japan
Univ. of Cergy-Pontoise, France
<EMAIL_ADDRESS>
&Ryota Torishima
Waseda Univ. & AIST, Japan
<EMAIL_ADDRESS>
&Kuniyuki Takahashi
Preferred Networks, Japan
<EMAIL_ADDRESS>
&Shoichiro Yamaguchi
Preferred Networks, Japan
<EMAIL_ADDRESS>
&Daisuke Okanohara
Preferred Networks, Japan
<EMAIL_ADDRESS>
&Tetsuya Ogata
Waseda Univ. & AIST, Japan
<EMAIL_ADDRESS>

###### Abstract

We show a new method for collision-free path planning by cGANs by mapping its
latent space to only the collision-free areas of the robot joint space. Our
method simply provides this collision-free latent space after which any
planner, using any optimization conditions, can be used to generate the most
suitable paths on the fly. We successfully verified this method with a
simulated two-link robot arm.

> Keywords: Path Planning, Collision Avoidance, Deep Learning

##  1 Introduction

Collision-free path planning is essential to ensure safety and to prevent the
robot from harming itself and its surroundings. There are three important
factors in robot path planning: i )  _Adaptation_ , ii )  _Customizability_ ,
and iii )  _Scalability of computation_. i ) Robots need to adapt quickly to a
new situation, which requires appropriate path planning for the placement of
unknown obstacles. ii ) Robots need to be customizable for different
situations. There are multiple (infinite) paths from a given start to a goal,
and it is necessary to choose the optimal path depending on the environment
and situation. In the real environment, we want to perform path planning not
only to avoid collision-obstacles, but also to satisfy other criteria such as
the efficiency of the robot‘s movements and the speed of its movements. iii )
These path planning operations should be calculable, even when there is a
large number of obstacles, since it generally takes a long time to collision-
check for obstacles. In other words, calculation time should scale well with
the number of obstacles.

It is challenging to meet these three requirements in existing methods (see
Section 2). Contrary to traditional planning in Cartesian or joint space, we
propose to plan within a new collision-free space. This method uses
Conditional Generative Adversarial Networks (cGANs) to map its latent space to
only the collision-free areas of the robot joint space, such that the robot
does not collide with obstacles if a path is planned within this latent space
(See Figure 1). That is, selecting any point in the latent space yields a
certain robot pose that does not collide with obstacles. The mappings from the
latent space to joint space _adapt_ to obstacles that are given to the cGANs
as conditions. GANs are used because it is a powerful generative model and its
latent space can be freely determined in advance; GANs are also highly
customizable. Because the latent space is collision-free and any point on a
line connecting any two points is also within this latent space (since this is
a convex space), a collision-free path can be generated by connecting the
start and goal points with any arbitrary line or curve in the latent space
within a domain of definition. Then, the joint trajectory corresponding to the
trajectory planned in latent space is acquired through the learned mappings.
Since we separated the learning of the mappings and the actual path planning
(or trajectory including optimizations), we can generate any trajectory we
want on the fly, for any optimization parameters that we want without
considering collisions, making our method highly _customizable_. Furthermore,
the computation cost does not depend on the number of obstacles because it
does not require collision detection, making its computation _scalable_. We
verify this method on a simulated 2D robot arm.

Figure 1:  Collision-free path planning for robot arm using latent space of
cGANs. Latent variables $\bm{z}_{s}$ and $\bm{z}_{g}$ that correspond to the
start $\bm{\theta}_{s}$ and goal $\bm{\theta}_{g}$ postures of the robot arm.
Any path in the latent space $\bm{z}_{s}:\bm{z}_{g}$ is mapped to the
collision-free path in the joint space $\bm{\theta}_{s}:\bm{\theta}_{g}$ by
using Generator ${G}$ with condition $\bm{c}$ as obstacles information.

##  2 Related Works

There are mainly two types of path planning methods: model-based and learning-
based methods. The following two model-based methods are the most common:
Design functions for obstacles and goals (e.g., potential fields [1, 2]),
search and optimization (e.g. RRT [3, 4] and $A^{\ast}$ [5]). Methods which
are a combination of these are also proposed and generally show improved
results [6, 7, 8, 9]. While model-based methods can reliably avoid obstacles,
their adaptability to various environments in real-time is limited since these
methods require specific function design and adjustment of parameters for each
situation in advance, not to mention the huge computational searching cost. In
addition, sometimes certain conditions need to be optimized depending on the
purpose, such as the shortest traveling distance in end-effector space or
joint space [10] or minimum jerk change [11]; usually multiple or infinite
paths for the same start and goal states exist, each of them optimized for
different purposes. As model-based methods are usually calculated according to
certain conditions/criteria in advance, other calculations need to be
performed when these criteria change. In other words, model-based methods lack
_scalability_ and _customizability_. The data collected by the model-based
methods can be used to train learning-based algorithms, particularly deep
learning [12, 13, 14, 15, 16, 17, 18]. These algorithms can infer a path for a
new environment in a short time if it has trained sufficiently in advance.
However, learning-based methods have the challenge that only one or a few
paths can be generated, and what kind of paths are generated depends on the
training data. For example, if naive RRT is used as training data, only
collision-free paths to the goal will be generated during inference, usually
without taking any additional constraints into account that naive RRT also
does not. Usually, learning-based methods lack _customizability_.

In [19, 20], the authors studied the generation of multiple trajectories.
Since the target of [19] was to generate various trajectories in environments
with no obstacles, obstacle avoidance was out of their scope. Our proposed
method is to plan paths in a collision-free space which are mapped from the
latent space to joint space. Since the trajectory of [20] is fixed once it is
generated, at best, only the optimal trajectory among the ones generated can
be selected, which is not necessarily the best for the situation at hand.
Thus, they have to generate trajectories until one of them satisfies the
criteria necessary for the situation, but they are generated randomly and the
method does not provide a way to define optimality. To address this issue, our
method does not directly output the trajectories, but simply provides a
collision-free space after which any planner, using any optimization
conditions, can be used to generate the most suitable paths.

The contribution of this research is to realize optimized path planning with
the three important factors; i )  _Adaptation_ , ii )  _Customizability_ , and
iii )  _Scalability of computation_.

##  3 Proposed Method

We propose a method that maps the latent space of cGANs to the collision-free
area of the robot joint space, so that the robot learns not to collide with
obstacles. Thus, any planned path in that latent space can be associated with
a collision-free path in joint space. The mapping from the latent space to
joint space _adapts_ accordingly to the obstacles given to cGANs as
conditions. Unlike path planners in joint space, since the mapping and path
planning phases are separated, any path planner can be used in the trained
latent space (where any point is collision-free) without taking obstacles into
account since there simply are none in the latent space, making our method
highly _customizable_. The computational cost is also lower since collision
check calculations are no longer necessary, making our method also _scalable_.
The correspondence from the latent space to joint space is trained by cGANs,
which uses a min-max game between a Generator ($G$) and a Discriminator ($D$),
and both are optimized alternately with the following objective function:

$\min_{G}\max_{D}V\left(D,G\right)=\mathcal{L}_{\mathrm{GAN}}\left(D,G\right)+\mathcal{L}_{\mathrm{collision}}\left(D\right)+\mathcal{L}_{\mathrm{identity}}\left(G\right)$
(1)

  1. 1.

$\mathcal{L}_{\mathrm{GAN}}$: The main loss function to learn the mapping from
the latent space to joint space.

  2. 2.

$\mathcal{L}_{\mathrm{collision}}$: Loss function to learn various situations
with obstacle, with less collision than non-collision data.

  3. 3.

$\mathcal{L}_{\mathrm{identity}}$: Loss function to learn from the latent
space to joint space continuously without “twist” or “distortion”. In
addition, for the purpose of path planning using a robot arm, rapid or sudden
changes in movement are discouraged.

Figure 2: Structure of collision-free path planning model using cGANs.

###  3.1 $\mathcal{L}_{\mathrm{GAN}}$: Acquisition of Latent Expression

To acquire the correspondence from the latent space to joint space, cGANs are
used. In GANs [21], latent expressions are acquired by training two models, a
Generator and a Discriminator, alternately. The Generator creates data
variables $\bm{\theta}_{\mathrm{model}}$ from latent variables $\bm{z}$. The
Discriminator estimates whether given variables are a sample from the data set
$\bm{\theta}_{\mathrm{non\mathchar 45\relax collision}}$ or a generated sample
$\bm{\theta}_{\mathrm{model}}$ calculated from $\bm{z}$, which is uniformly
sampled from the latent space within [0,1]. Since the latent space is a convex
space and the boundaries of the latent space can be arbitrarily determined in
advance, any point of a line segment connecting any point is in that latent
space, within a domain of definition. Furthermore, it is possible to give
conditions to the models by introducing a $Condition$ variable $\bm{c}$ [22].

Figure 2 shows the concept of the proposed network model. Through the
Generator, the mapping from the latent space to collision-free joint space is
obtained. The Discriminator identifies the joint angles, generated by the
Generator $\bm{\theta}_{\mathrm{model}}$, and the actual sampled joint angles,
$\bm{\theta}_{\mathrm{non\mathchar 45\relax collision}}$. In condition
$\bm{c}$, the obstacle information is given as a binary mask showing the
location of the obstacle. This condition $\bm{c}$ is connected to the
Generator and the Discriminator, so that when the given obstacle mask changes,
the correspondence from the latent space to joint space changes. In other
words, our method does not need to prepare a different network for each
obstacle, and only one cGANs can support multiple obstacle environments.

The loss function, $\mathcal{L}_{\mathrm{GAN}}$, for training cGANs is shown
in equation (2).

$\begin{split}\mathcal{L}_{\mathrm{GAN}}(D,G)=&\mathbb{E}_{\bm{c}\sim
p_{\mathrm{obstacles}}\left(\bm{c}\right),\,\bm{\theta}\sim
p_{\mathrm{non\mathchar 45\relax
collision}}\left(\bm{\theta}|\bm{c}\right)}\left[\log
D\left(\bm{\theta},\bm{c}\right)\right]\\\ &+\mathbb{E}_{\bm{c}\sim
p_{\mathrm{obstacles}}\left(\bm{c}\right),\,\bm{z}\sim
p_{\bm{z}}\left(\bm{z}\right)}\left[\log\left(1-D\left(G\left(\bm{z},\bm{c}\right),\bm{c}\right)\right)\right]\end{split}$
(2)

Where $p_{\mathrm{obstacles}}(\bm{c})$ is the distribution of obstacles
positions and $p_{\mathrm{non\mathchar 45\relax
collision}}(\bm{\theta}|\bm{c})$ is the distribution of non-collision joint
angles which the Generator should aim to generate. $p_{\bm{z}}(\bm{z})$ is the
uniform distribution in the latent space.

###  3.2 $\mathcal{L}_{\mathrm{collision}}$: Adaptation to Multiple Obstacle
Conditions

In this section, we describe how to adapt to various obstacle conditions. Even
though collision-free mapping from the latent space to joint space is trained
by equation (2), the network cannot learn well since the number of non-
collision data points is much smaller than those with collisions. As the
obstacles become more diverse, there is a risk of mistaking collision points
for non-collision points and vice versa.

It is therefore necessary to train with the collision joints explicitly
incorporated within the equation. The loss function,
$\mathcal{L}_{\mathrm{collision}}$, shown in equation (3) is introduced in
order to provide the data of the collision joints to the Discriminator.

$\mathcal{L}_{\mathrm{collision}}(D)=\mathbb{E}_{\bm{c}\sim
p_{\mathrm{obstacles}}\left(\bm{c}\right),\,\bm{\theta}\sim
p_{\mathrm{collision}}\left(\bm{\theta}|\bm{c}\right)}\left[\log\left(1-D\left(\bm{\theta},\bm{c}\right)\right)\right]$
(3)

Where $p_{\mathrm{collision}}(\bm{\theta}|\bm{c})$ is the distribution of
joint angles that collide with obstacles, which the Generator should thus
refrain from generating. The Discriminator is trained to output $0$ for
collision joints and $1$ for collision-free joints for each obstacle.
Furthermore, the Generator is trained to acquire a distribution to make the
Discriminator output $1$, as we are trying to obtain a distribution for
collision-free space.

###  3.3 $\mathcal{L}_{\mathrm{identity}}$: Specifying the Map from the Latent
Space to Joint Space

We will describe in this section how to map from the latent space to joint
space, such that arbitrary planned paths in the latent space are smooth in
joint space for robot arms. In equation (2), the path planned in the latent
space is mapped from each point in the latent space to joint space, but it is
not certain whether the path planned in the latent space can be realized by
the robot in joint space. The mapping from the latent space to joint space has
to be continuous without “twists”,“distortions”, and rapid changes. In order
to achieve this, the following two things are performed:

  * •

The number of dimensions for latent variables is matched to the number of
robot joints; each latent variable is mapped to represent each joint, and the
normalized ranges of latent variables and joint angles are aligned.

  * •

The Generator is trained to output $\bm{\theta}$ when the latent variables
$\bm{z}=\bm{\theta}$ are given as input of the Generator. In other words, a
certain distance in the latent space is almost the same distance in joint
space.

However, since the acquired map may be distorted in order to avoid collisions,
these constraints are not added to the joint that collides with the obstacles.
The loss function, $\mathcal{L}_{\mathrm{identity}}$, for training cGANs is
shown in equation (4).

$\mathcal{L}_{\mathrm{identity}}(G)=\mathbb{E}_{\bm{c}\sim
p_{\mathrm{obstacles}}\left(\bm{c}\right),\,\bm{\theta}\sim
p_{\mathrm{non\mathchar 45\relax
collision}}\left(\bm{\theta}|\bm{c}\right)}\left[\|G\left(\bm{z}=\bm{\theta},\bm{c}\right)-\bm{\theta}\|_{2}^{2}\right]$
(4)

##  4 Experiment

The purpose of the experiment is to confirm three factors, i )  _Adaptation_ ,
ii )  _Customizability_ , and iii )  _Scalability_ , by the proposed mapping
function from the latent space to joint space acquired by training cGANs. We
performed an experiment using a simulation of a two-link arm robot as the
simplest example to analyze the results in detail.

###  4.1 Robot Setup

To perform our experiments, we use a simulation of a two-link robot arm (See
Figure 3 (a)). The joint angles of the first and second axes are $\theta_{1}$
and $\theta_{2}$, respectively, and the length of each link of the arm is
$1.0$. The range of each joint angle is
$\theta_{1}\in[-90^{\circ},90^{\circ}]$ and
$\theta_{2}\in[5^{\circ},150^{\circ}]$. Considering the $xy$ plane with the
first joint of the robot as the origin, the obstacles are arranged in a grid
pattern in the range of $-1.0\leq x\leq 2.0$, $-2.0\leq y\leq 2.0$ (See Figure
3 (b)).

Figure 3:  (a) A simulator of a two-link robot arm with parameters, (b) an
example of an environment with obstacles. No obstacles are placed in the red
area to avoid narrowing the robot’s workspace.

###  4.2 Data Collection

We will describe the details of how the data was collected in the following
subsections.

####  4.2.1 Robot movement

The training data of cGANs consists of two joint angles
$\bm{\theta}=(\theta_{1},\theta_{2})$ that represents the posture of a two-
link robot arm. The latent variables $\bm{z}$ are also two-dimensional because
the robot has 2-DoF, and a uniform distribution in the range $[0,1]$ is used.
The step sizes for sampling the joint angles are both set to $5^{\circ}$.
$37\times 30=1110$ data points for each obstacle condition is created. Min-Max
scaling was applied to each of $\theta_{1},\theta_{2}$, and both were
normalized to the range of $[0,1]$.

####  4.2.2 Obstacle Position

The position of the obstacle is given as a binary mask as Condition $\bm{c}$,
and a position occupied by the obstacle is represented as $1$, and an
unoccupied position is represented by $0$. The Condition $\bm{c}$ is a two-
dimensional array of $32\times 24$. Obstacles are placed in specific units by
randomly deciding the position and size of a circle or rectangle with a
minimum size of 0.15 in length and 0.15 in width. However, there is a
constraint that prevents obstacles from being placed in places that greatly
obstruct the movement of the robot, in order to prevent the robot’s workspace
from being too narrow (See Fig. 3(b)). For collision detection, we checked
whether the four sides of each obstacle intersects with either of the two
links of the robot arm.

####  4.2.3 Dataset

There is one dataset without obstacle conditions and 1,000 datasets with
obstacle conditions. 5-fold cross-validation is performed using $800$ for
training and $200$ for evaluation.

###  4.3 Network Design

The architecture of our network model is composed of a Generator and a
Discriminator with fully connected layers, and each network includes a two-
dimensional convolutional layer as a feature extraction unit for Conditions
(See Figure 2). For learning stabilization, batch normalization [23], spectral
normalization [24], and feature matching [25] were used. Our network model is
implemented with Chainer [26] as deep learning library and detailed parameters
are shown in the supplemental material. Training is conducted on a machine
equipped with Intel Core i9-7900X CPU and GeForce RTX 2080, resulting in about
1 to 1.5 days of training time.

##  5 Results

###  5.1 Mapping from Latent Space to Joint Space

We first show examples of the mapping from the latent space to joint angle
space acquired by learning (Figure 4). Areas in the latent space that
correspond with areas in joint space are shown in the same colors. We can
observe that approximately $z_{1}$ and $\theta_{1}$ and $z_{2}$ and
$\theta_{2}$ have a corresponding relationship between the latent space and
obstacle-free joint space (See the latent space and joint space without
obstacles, condition $\bm{c}_{0}$, in Figure 4). It can also be seen that the
mapping from latent space to joint space corresponds to each other
continuously, without torsions or distortions. Additionally, the mapping was
generated while avoiding the obstacles’ areas according to the given
conditions.

Figure 4:  Acquired mappings from latent space to joint space with different
obstacle positions, $\bm{c}_{0}\sim\bm{c}_{3}$. Areas in the latent space that
correspond with areas in joint space are shown in the same colors. The gray
area in the joint space represents the joint angles that collide with
obstacles.

###  5.2 Collision-free Path Planning

Here, we show examples of collision-free path planning in the latent space.
Figure 5 shows the result of mapping planned paths in the latent space to
joint space when an untrained condition is given (See more examples in the
attached video). Any planned paths in the latent space is collision-free in
joint space. The path planning sometimes failed because it touched the surface
of the obstacle at the collision/non-collision boundary. In the next section,
we will describe how accurate it is.

Figure 5:  Examples of path planning in latent space for untrained conditions.
(a) the latent space, (b) the joint space, and (c) the $xy$ space. The paths
of the same color in the latent space and the joint space correspond to each
other. The blue planned path is also shown in $xy$ space.

###  5.3 Quantitative Evaluation of Acquired Mapping

We evaluate the accuracy of the mapping acquired from the Generator to verify
i )  _Adaptation_. Both joint and the latent spaces are divided at regular
intervals into a grid, by $\Delta\theta$ and similar values from the latent
space. Joint angles are generated by the Generator by sampling one point from
each grid point in the latent space. The generated joint angles are assigned
to the corresponding grid points in joint space. Of all the grid points in the
joint space, we counted the following numbers:

  * •

the grid points that avoid collisions are True Positive (TP),

  * •

the grid points that do not avoid collisions but are not generated is False
Negative (FN),

  * •

and the grid points that do not avoid collisions but are generated, are False
Positive (FP).

Using these numbers, the accuracy was evaluated by following two metrics: 1)
the overlapping area between the joint space area that avoided collisions and
the area generated by the Generator (calculated by equation (5)) using the
Intersection over Union (IoU), 2) the proportion of the joint angles generated
by the Generator that actually avoided collisions (calculated by equation (6)
as precision) (See Figure 6 as an example of the process for calculating
metrics.)

$\displaystyle\mathrm{IoU}\left(G,\,\bm{c}\right)$ $\displaystyle=$
$\displaystyle\mathrm{TP}/(\mathrm{TP}+\mathrm{FP}+\mathrm{FN})$ (5)
$\displaystyle\mathrm{Precision}\left(G,\,\bm{c}\right)$ $\displaystyle=$
$\displaystyle\mathrm{TP}/(\mathrm{TP}+\mathrm{FP})$ (6)

Table 1 shows the average value of IoU and the precision in 5-fold cross
validation. The results depend on the size of the grid points, but we
confirmed that the results converged when $\Delta\theta=1^{\circ}$ and the
total number of samples $N$ was $26,426$. The average value of IoU between
trained and untrained conditions is similar to the distribution of joint
angles that avoid collisions. The average precision in both trained and
untrained conditions is high. We performed 5-fold cross-validation and select
the best IoU averages, shown in Figure 1 as a histogram. The relative
frequency on the vertical axis is divided by the number of data points (801
training and 200 test data points). The IoU is around $0.6$ in many conditions
for both the training data and the test data, but the histogram spreads to the
left in the test data, which means the value of IoU is worse on some
Conditions in the test data. This result suggests that our single trained
model can adapt to multiple obstacle conditions including untrained ones.

Figure 6:  An example of the metric calculation process. The joint angle space
is divided into grids. Each point is marked Positive/Negative which indicates
whether the point is generated by $G$ or not and True/False, which indicates
whether the output is correct or not.

Table 1: Statistics of accuracy of the mapping by the Generator in the 5-fold
cross-validation.

| IoU
---|---
| mean | std | min | max
Train | 0.493 | 0.022 | 0.407 | 0.549
Test | 0.491 | 0.024 | 0.404 | 0.543
| Precision
| mean | std | min | max
Train | 0.990 | 0.006 | 0.947 | 0.997
Test | 0.986 | 0.013 | 0.904 | 0.997

Figure 7:  A histogram of the best IoU averages from 5-fold cross validation.

###  5.4 Path Selection in the Latent Space

Here, we verify ii )  _Customizability_ and iii )  _Scalability_. The proposed
method can generate multiple (in-finite) paths. No matter what kind of path is
planned in the latent space, the result is mapped to the corresponding
collision-free path in joint space. The method for determining paths in the
latent space is not limited to just connecting the start and the goal
linearly, but can be any path/trajectory planner; this makes our method highly
_customizable_ since we can use anything we want. One idea is to use graph
optimization for the shortest traveling distance in joint space. Figure 8
shows the result of constructing a graph from neighboring points in the latent
space and performing $A^{\ast}$ optimization in joint space. The heuristic
function used is the Euclidean distance. Nodes of the graph are uniformly
sampled in $z_{1},z_{2}$ and a total of $N=128\times 128=16,384$.

Figure 9 shows the relationship between the total area of obstacles and CPU
calculation time for the number of nodes described above. The computational
cost for collision checks increases as the number of obstacles increases and
as the shapes become complicated, but the computational cost of the inference
by the Generator does not depend on the obstacles after the learning phase
since collision checks are not required, making the computations _scalable_ to
the number of obstacles. The inference by the Generator for $16,384$ latent
variables is computed by the GPU in 0.119 seconds.

Figure 8:  One of the examples of the optimized path. The red path is
optimized for the shortest traveling distance in joint space by $A^{\ast}$,
and the blue path is a straight line in the latent space.  Figure 9:  (a) The
relationship between the number of obstacles and the calculation time. In
order to reduce the effect of program performance, we used the ratio of CPU
time to computation time for each label under the simplest obstacle condition,
(b).

##  6 Discussion about Application to High-DoF Robots

The proposed method can be used for robots with higher DoF. In this research,
we conducted experiments using a two-link robot arm accompanying 2-dimensional
latent space. The proposed network model can be applied if the dimension of
the latent space is increased according to the DoF of the robot. The condition
variables can be given in 3D, so 3D convolution can be applied.

One of the main challenges is that the training dataset size will increase as
the number of dimensions increases. In this study, the robot was trained in
the entire motion range of the robot, but by targeting the work and motion
range with a focus on specific tasks, the data size can be reduced.

##  7 Conclusion

In this research, the robot’s collision-free joint angles are expressed as the
latent space of cGANs, and collision-free paths are obtained by mapping the
path planned in the latent space to joint space. It was confirmed that i )
_Adaptation_ ; a single trained model could handle multiple unknown obstacle
conditions, ii )  _Customizability_ ; any path can be planned in the latent
space, and iii )  _Scalability_ ; computational cost of path planning does not
depend on the obstacles. As for future prospects, we are considering the
application of this method to higher DoF robots as discuss in section 6.

#### Acknowledgments

The authors would like to thank Wilson Ko for helping writting and
proofreading. Hiroki Mori would like to thank all colleagues in ETIS lab in
the University of Cergy-Pontoise, especially Prof. Mathias Quoy, Prof.
Philippe Gaussier and Assoc. Prof. Alexandre Pitti because he came up with the
basic idea of this article and discussed a preliminary result with them when
he joined the lab in 2016.

## References

  * Warren [1990] C. W. Warren.  Multiple robot path coordination using artificial potential fields.  In _Proceedings., IEEE International Conference on Robotics and Automation_ , pages 500–505 vol.1, May 1990.  doi:10.1109/ROBOT.1990.126028.
  * Li et al. [2012] G. Li, A. Yamashita, H. Asama, and Y. Tamura.  An efficient improved artificial potential field based regression search method for robot path planning.  In _2012 IEEE International Conference on Mechatronics and Automation_ , pages 1227–1232, 2012.
  * Lavalle [1998] S. M. Lavalle.  Rapidly-exploring random trees: A new tool for path planning.  Technical report, 1998.
  * LaValle and James J. Kuffner [2001] S. M. LaValle and J. James J. Kuffner.  Randomized kinodynamic planning.  _The International Journal of Robotics Research_ , 20(5):378–400, 2001.  doi:10.1177/02783640122067453.  URL https://doi.org/10.1177/02783640122067453.
  * Hart et al. [1968] P. E. Hart, N. J. Nilsson, and B. Raphael.  A formal basis for the heuristic determination of minimum cost paths.  _IEEE Transactions on Systems Science and Cybernetics_ , 4(2):100–107, 1968.
  * Naderi et al. [2015] K. Naderi, J. RajamÃ¤ki, and P. HÃ¤mÃ¤lÃ¤inen.  Rt-rrt*: a real-time path planning algorithm based on rrt*.  pages 113–118, 11 2015.  doi:10.1145/2822013.2822036.
  * Qureshi and Ayaz [2015] A. H. Qureshi and Y. Ayaz.  Intelligent bidirectional rapidly-exploring random trees for optimal motion planning in complex cluttered environments.  _Robotics and Autonomous Systems_ , 68:1 – 11, 2015.  ISSN 0921-8890.  doi:https://doi.org/10.1016/j.robot.2015.02.007.  URL http://www.sciencedirect.com/science/article/pii/S0921889015000317.
  * Qureshi and Ayaz [2017] A. H. Qureshi and Y. Ayaz.  Potential functions based sampling heuristic for optimal path planning.  _CoRR_ , abs/1704.00264, 2017.  URL http://arxiv.org/abs/1704.00264.
  * Tahir et al. [2018] Z. Tahir, A. H. Qureshi, Y. Ayaz, and R. Nawaz.  Potentially guided bidirectionalized rrt* for fast optimal path planning in cluttered environments.  _Robotics and Autonomous Systems_ , 108:13 – 27, 2018.  ISSN 0921-8890.  doi:https://doi.org/10.1016/j.robot.2018.06.013.  URL http://www.sciencedirect.com/science/article/pii/S0921889017309387.
  * Lalibertk and Gosselin [1994] T. Lalibertk and C. M. Gosselin.  Efficient algorithms for the trajectory planning of redundant manipulators with obstacle avoidance.  In _Proceedings of the 1994 IEEE International Conference on Robotics and Automation_ , pages 2044–2049, 5 1994.
  * Flash and Hogan [1985] T. Flash and N. Hogan.  The coordination of arm movements: an experimentally confirmed mathematical model.  _Journal of Neuroscience_ , 5:1688–1703, 1985.
  * Srinivas et al. [2018] A. Srinivas, A. Jabri, P. Abbeel, S. Levine, and C. Finn.  Universal planning networks: Learning generalizable representations for visuomotor control.  In J. Dy and A. Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 4732–4741, StockholmsmÃ¤ssan, Stockholm Sweden, 10–15 Jul 2018. PMLR.  URL http://proceedings.mlr.press/v80/srinivas18b.html.
  * Tamar et al. [2016] A. Tamar, S. Levine, and P. Abbeel.  Value iteration networks.  _CoRR_ , abs/1602.02867, 2016.  URL http://arxiv.org/abs/1602.02867.
  * Ichter et al. [2018] B. Ichter, J. Harrison, and M. Pavone.  Learning sampling distributions for robot motion planning.  In _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , pages 7087–7094. IEEE, 2018.
  * Wang et al. [2019] A. Wang, T. Kurutach, K. Liu, P. Abbeel, and A. Tamar.  Learning robotic manipulation through visual planning and acting.  _CoRR_ , abs/1905.04411, 2019.  URL http://arxiv.org/abs/1905.04411.
  * Kumar et al. [2019] R. Kumar, A. Mandalika, S. Choudhury, and S. S. Srinivasa.  Lego: Leveraging experience in roadmap generation for sampling-based planning.  _arXiv preprint arXiv:1907.09574_ , 2019.
  * Terasawa et al. [2020] R. Terasawa, Y. Ariki, T. Narihira, T. Tsuboi, and N. Nagasaka.  3d-cnn based heuristic guided task-space planner for faster motion planning.  In _2020 International Conference on Robotics and Automation (ICRA)_ , pages 9548–9554. IEEE, 2020.
  * Ota et al. [2020] K. Ota, Y. Sasaki, D. K. Jha, Y. Yoshiyasu, and A. Kanezaki.  Efficient exploration in constrained environments with goal-oriented reference path.  _arXiv preprint arXiv:2003.01641_ , 2020.
  * Kutsuzawa et al. [2019] K. Kutsuzawa, H. Kusano, A. Kume, and S. Yamaguchi.  Motion generation considering situation with conditional generative adversarial networks for throwing robots.  _arXiv preprint arXiv:1910.03253_ , 2019.
  * Qureshi et al. [2018] A. H. Qureshi, M. J. Bency, and M. C. Yip.  Motion planning networks.  _CoRR_ , abs/1806.05767, 2018.  URL http://arxiv.org/abs/1806.05767.
  * Goodfellow et al. [2014] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio.  Generative adversarial nets.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems 27_ , pages 2672–2680. Curran Associates, Inc., 2014.  URL http://papers.nips.cc/paper/5423-generative-adversarial-nets.pdf.
  * Mirza and Osindero [2014] M. Mirza and S. Osindero.  Conditional generative adversarial nets.  _CoRR_ , abs/1411.1784, 2014.  URL http://arxiv.org/abs/1411.1784.
  * Ioffe and Szegedy [2015] S. Ioffe and C. Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37_ , ICML’15, page 448â456. JMLR.org, 2015.
  * Miyato et al. [2018] T. Miyato, T. Kataoka, M. Koyama, and Y. Yoshida.  Spectral normalization for generative adversarial networks.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=B1QRgziT-.
  * Salimans et al. [2016] T. Salimans, I. Goodfellow, W. Zaremba, V. Cheung, A. Radford, X. Chen, and X. Chen.  Improved techniques for training gans.  In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, editors, _Advances in Neural Information Processing Systems 29_ , pages 2234–2242. Curran Associates, Inc., 2016.  URL http://papers.nips.cc/paper/6125-improved-techniques-for-training-gans.pdf.
  * Tokui et al. [2015] S. Tokui, K. Oono, S. Hido, and J. Clayton.  Chainer: a next-generation open source framework for deep learning.  In _Proceedings of Workshop on Machine Learning Systems (LearningSys) in The Twenty-ninth Annual Conference on Neural Information Processing Systems (NIPS)_ , 2015.