[longplural=Code Generation Tools]cgtCGTCode Generation Tool
[longplural=Common Weakness Enumerations]cweCWECommon Weakness Enumeration
cveCVECommon Vulnerabilities and Exposures [longplural=Large Language
Models]llmLLMLarge Language Model [longplural=Recurrent Neural
Networks]rnnRNNRecurrent Neural Network nlpNLPNatural Language Processing
[longplural=Long Short-Term Memories]lstmLSTMLong Short-Term Memory

# Copilot Security: A User Study

Owura Asare  University of WaterlooWaterlooCanada<EMAIL_ADDRESS>,  N.
Asokan  University of WaterlooWaterlooCanada<EMAIL_ADDRESS>and  Meiyappan
Nagappan  University of WaterlooWaterlooCanada<EMAIL_ADDRESS>
(2018)

###### Abstract.

Code generation tools driven by artificial intelligence have recently become
more popular due to advancements in deep learning and natural language
processing that have increased their capabilities. The proliferation of these
tools may be a double-edged sword because while they can increase developer
productivity by making it easier to write code, research has shown that they
can also generate insecure code. In this paper, we perform a user-centered
evaluation GitHub’s Copilot to better understand its strengths and weaknesses
with respect to code security. We conduct a user study where participants
solve programming problems (with and without Copilot assistance) that have
potentially vulnerable solutions. The main goal of the user study is to
determine how the use of Copilot affects participants’ security performance.
In our set of participants (n=25), we find that access to Copilot accompanies
a more secure solution when tackling harder problems. For the easier problem,
we observe no effect of Copilot access on the security of solutions. We also
observe no disproportionate impact of Copilot use on particular kinds of
vulnerabilities.

user study, code generation, copilot, security, software engineering

††copyright: acmcopyright††journalyear: 2018††doi: XXXXXXX.XXXXXXX††ccs:
Security and privacy Software security engineering††ccs: Computing
methodologies Natural language generation

##  1\. Introduction

have recently become more popular due to their ability to make developers more
productive during the software development process. By , we refer to and their
fine-tuned descendants that are used to generate code. These tools have
improved as a result of progress in deep learning and natural language
processing that have made it possible to train increasingly more capable large
language models in an efficient manner.

have the ability to become large scale producers of insecure code if left to
grow unchecked. This is because are trained on code sourced from repositories
that lack security guarantees, making it probable that they are trained on
code segments with potential security vulnerabilities. This in turn leads to
the possible production of insecure code when these are used by developers.
Empirical evidence by Pearce et al. (Pearce et al., 2022) substantiates this
claim, revealing that GitHub’s Copilot(GitHub Inc., 2021), a widely-used based
on the Codex (Chen et al., 2021), produces insecure code approximately 40% of
the time.

To mitigate the possible adverse effects of , it is important that we gain a
deeper understanding of their impacts on security. In this paper, we present
our work on a user-centered security evaluation of GitHub’s Copilot that aims
to provide a better understanding of how affect code security. We investigate
how Copilot (when used as an assistant) affects users’ security performance by
designing and conducting a user study where participants solve programming
problems with and without the assistance of Copilot. We observe that
participants in our sample generally have a better security performance when
access to Copilot is granted for difficult problems, and less so for
relatively simpler problems. We also observe a more uniform performance across
the different types of vulnerabilities when Copilot is in use. By this we mean
that the presence of Copilot does not seem to disproportionately influence the
presence or absence of any type of vulnerability. Overall, our results suggest
that:

  1. (1)

the security utility of (specifically Copilot) is enhanced in the face of
challenging problems (Section 5.2)

  2. (2)

the use of Copilot does not necessarily increase or reduce the chances of any
particular vulnerability (Section 5.3)

We provide access to all our study material at
https://github.com/ppdb1123/copilot-user-study-supp

##  2\. Background

###  2.1. Language Models and Code Generation

Language models are generally defined as probability distributions over
sequences of words. Language models model language by probabilistically
predicting/generating the next word in a given sequence. They are able to do
this by leveraging a set of parameters that are obtained after training on
significant amounts of data. Over time, language models have evolved, from
non-neural models (N-grams), to neural, recurrence-based models (RNNs) (Bengio
et al., 2000), to attention-based models (Transformers) (Vaswani et al.,
2017).

The evolution and rise in popularity of language models have led to their
applications to several tasks across many domains. One such domain is software
engineering where language models have been put to the task of code
generation. , available either through integrated development environments
(IDEs) or as extensions to text editors, are already widely used by developers
(Dohmke, 2022) and they continue to evolve in complexity. GitHub’s Copilot
(GitHub Inc., 2021) is an example of an evolved . Copilot is generally
described as an AI pair programmer trained on billions of lines of public
code. Currently available as an extension for the VSCode text editor, Copilot
takes into account the surrounding context of a program and generates possible
code completions for the developer. IntelliCode (Svyatkovskiy et al., 2020) is
another example of a that generates recommendations based on thousands of
open-source projects on GitHub.

Most current high performing models use the Transformer model which was
initially introduced with two components: an encoder and a decoder. There are,
however, high performing models that either only use the encoder (Devlin et
al., 2019) or the decoder (Brown et al., 2020). Copilot is based on OpenAI’s
Codex (Chen et al., 2021), which is itself a fine-tuned version of GPT-3
(Brown et al., 2020).

###  2.2. Security Evaluations

There are a number of studies that have evaluated Copilot and other tools like
it that focus non-security metrics such as understandability, usability and
productivity (Chen et al., 2021; Li et al., 2022; Xu et al., 2022; Erhabor,
Daniel, 2022; Nguyen and Nadi, 2022; Ziegler et al., 2022). There are also
some security focused evaluations of Copilot (Pearce et al., 2022) and, even
more pertinent to this paper, two security-focused user studies (not of
Copilot, but of large language models for code generation) (Sandoval et al.,
2023; Perry et al., 2022). We discuss the differences in methodology and
findings between the three existing user studies and findings in the related
works (Section 8).

##  3\. Research Overview

###  3.1. Motivation

are designed to assist programmers during the code writing phase of the
software development process. In this paper, we are interested in how Copilot
affects the security of code written by the human participants in our user
study. While there is existing research on evaluating LLM-based code
assistants (Sandoval et al., 2023; Perry et al., 2022), ours is the first to
focus on Copilot which is the more mature and fine-tuned . Copilot is also
more popular and more accessible, which makes our findings more likely to be
applicable to developers’ experience in non-experimental settings.

###  3.2. Research Questions

  1. (1)

Does Copilot use correlate with participants writing more secure code?

  2. (2)

Are there vulnerability types that Copilot is more susceptible to or more
resilient against?

##  4\. Method

Here we discuss our approach for the study. Figure 1 summarizes our method.

Figure 1. An overview of the user study, highlighting the key steps from
recruiting participants to analyzing results.

###  4.1. Participants: Recruitment and Screening

Participants for this study were recruited online via mailing lists. While our
main source of participants was a university [REDACTED] computer science
graduate student mailing list, we also extended invitations to industry
professionals and potentially qualified undergraduate students. Participants
who expressed interest in the study were asked to fill consent and screening
forms which we used to determine if they were suitable for the study.
Selection criteria for this study was based on age (over 18 years),
programming experience (at least one year of programming experience in C/C++),
access to Copilot, and employment history (people who had no affiliation with
the development of Copilot and had not been employed by GitHub or OpenAI).
Participants who met our selection criteria were then allowed to schedule a
two hour online study session for the experiment to be conducted.

Overall, 33 people expressed interest in taking part in the study. 8 of them
either did not complete the consent and screening process or did not select a
time for the problem solving session. 25 out of the 33 people completed all
stages of the study for a completion rate of 75%. The 25 participants were
made up of 4 undergraduate students (16%), 19 graduate students (76%), and 2
professionals (8%). A majority of our participants (19/21) described
themselves as “first time users” of Copilot, 5 of them indicated that they had
“tried it out a few times” and 1 indicated that they “used it all the time”.
This information is summarized in Table 2.

CWE-ID |  Description |  Problem S |  Problem T
---|---|---|---
CWE-20 |  Improper Input Validation |  ✓ |  ✓
CWE-22 |  Path Traversal |  |  ✓
CWE-78 |  OS Command Injection |  |  ✓
CWE-79 |  Cross-Site Scripting |  ✓ |
CWE-89 |  SQL Injection |  ✓ |  ✓
CWE-125 |  Out of Bounds Read |  ✓ |  ✓
CWE-285 |  Improper Authorization |  ✓ |  ✓
CWE-287 |  Improper Authentication |  ✓ |  ✓
CWE-401 |  Memory Leak |  ✓ |  ✓
CWE-415 |  Double Free |  ✓ |  ✓
CWE-416 |  Use After Free |  ✓ |  ✓
CWE-476 |  Null Pointer Dereference |  ✓ |  ✓
CWE-787 |  Out of Bounds Write |  ✓ |  ✓
Table 1. The list of that we specifically checked for in each problem.
Problems were designed such that the specified could be introduced if
participants were not careful enough about writing secure code.

###  4.2. Material: Programming Problems

####  4.2.1. Problem Design

We designed two problems for this study: problem S and problem T. In problem
S, the participants had to implement a sign-in function for an application
given a user’s identifier and password. In problem T, the participants had to
implement a function that performs a series of transactions in a given
transaction file and then renames the file.

We decided to create our own set of problems for this study as we had specific
criteria that called for tailored problems. Specifically, we sought problems
that:

  1. (1)

had potential for vulnerable solutions,

  2. (2)

had solutions that could manually be analyzed

  3. (3)

resembled real world applications

  4. (4)

could be solved by participants within an hour

In order to address criteria 1 and 2, we designed the problems so that certain
vulnerabilities could be introduced if participants were not careful with
their solutions. The vulnerabilities that could be introduced were based on .
The set of possible for each problem would subsequently be used for our
analysis of participant solutions. Table 1 contains the that we focused on for
each problem. Note that this set of is not exhaustive and there may be other
vulnerabilities possible in the problems we designed.

In order to address criteria 3 and 4, we created a collection of well
documented helper functions (with stub implementations) for each problem.
These helper functions enabled us to expand the level of difficulty of our
problems (approximating real world applications) while also constraining and
guiding users towards finding solutions within a confined solution space in
the allotted time.

###  4.3. Procedure

####  4.3.1. Problem Solving

Each participant involved in the study was programmatically assigned to one of
four groups on a round-robin basis. The groups determined the order in which
the problems were solved and whether Copilot would be used to solve problem S
or problem T. Participants were given 60 minutes to solve each problem
together with an instruction sheet that they could reference during problem
solving. Participants were informed (verbally and in the written instructions)
that they were to write secure code. There were no restrictions on the
resources participants could consult to aid in solving the problem other than
the restrictions on Copilot use and the use of other . Each participant’s
screen was recorded during problem solving for subsequent analysis after the
study session. All participants used Copilot in the Microsoft Visual Studio
Code text editor. Participants were free to use and interact with Copilot in
whatever manner they preferred. After each problem was finished the solutions
were saved. Then, participants were required to fill out surveys to provide
additional information about their perspective on the problem they just
completed. Upon completion of the study, each participant was compensated
CAD50.00.

####  4.3.2. Functionality Analysis

We tested solutions for functionality requirements with two of types tests:
basic tests and advanced tests. Participants had access to the basic test
during the study and had the option of testing their solutions on it if they
desired. They did not have access to the advanced test. To perform the basic
test, participants had to uncomment and run code provided for them in the main
function of the problem file. The basic tests tested participant solutions on
simple inputs, similar to what was described in the instructions. The advanced
testing involved checking participant solutions on edge-case and more complex
inputs such as null inner structs (problem S) and multiple transactions
(problem T).

####  4.3.3. Security Analysis

All solutions submitted by participants were checked for the presence of the
various possible for each problem (Table 1). This checking was performed
manually by one author and one other independent coder. We resorted to manual
analysis of participant solutions because it has been proven to be sufficient
when it comes to analyzing relatively short snippets of code (Pearce et al.,
2022; Perry et al., 2022; Siddiq and Santos, 2022). Other research that has
performed security analyses of code generated by has generally relied on
manual analysis or CodeQL (GitHub Inc., 2019a) to check for the presence of
vulnerabilities. We used manual analysis because our preliminary testing of
CodeQL showed that it was unable to detect any of the vulnerabilities in our
test samples - it always generated false negative results. To ensure that
CodeQL’s poor performance was not due to any misconfiguration of our CodeQL
setup, we performed additional tests to validate its setup. We used code
snippets provided in the CodeQL GitHub repository (GitHub Inc., 2019b) which
were known to contain certain . For these examples, CodeQL was able to
successfully identify the vulnerabilities. We also considered using fuzzing
for our analyses but decided against it due to the proven track record of
manual analysis and the use of stub helper functions in the programming
problems, which would make adopting fuzzing a costly endeavour with no
guarantee of better performance.

Solutions were analyzed independently by one of the authors and an independent
coder - a Computer Science PhD student in our department with experience in C
programming and vulnerability analysis. For each solution, both parties
checked for the presence of each of the in Table 1 and stored their results
separately. The results were subsequently cross-referenced to find situations
where the author and coder were in disagreement about the presence or absence
of a CWE in a solution. A vulnerability was only considered present or absent
in a solution if both the author and the coder were in agreement. Where there
were disagreements, the author and the coder discussed until a consensus was
reached. This was required in less than 5% of the cases. The manual analysis
of solutions resulted in a security score for the two problems solved by each
participant. The security score, outlined below, is a function of the number
of vulnerabilities present in a participant’s solution. For our purposes, a
solution with a higher security score is more secure than a solution with a
lower security score. The security score ranges from 0 (all vulnerabilities
found) to 100 (no vulnerabilities found). While the security score was
computed for all solutions, only those that compiled and passed the basic test
were used for subsequent analyses.

$PercentageVulnerable=\frac{\text{Number of Vulnerabilities
found}}{\text{Total number of Vulnerabilities Possible}}*100$

$\textbf{Security Score}=100-PercentageVulnerable$

###  4.4. Ethics

This user study obtained ethics clearance from the Human Research Ethics Board
at [REDACTED]. Participant consent was obtained during the recruitment process
and consenting participants were screened to ensure they met the desired
criteria. Participants were informed that their screens would be recorded
during the session. Data collected during sessions, including screen
recordings, problem solutions, and survey information, were linked to
anonymous IDs created for each participant. We maintained a key in a secure
vault linking participant information (name and email address) to IDs that
will be deleted once all analysis is complete and no further contact with
participants is required.

##  5\. Results and Discussion

Table 3 summarizes the data about participant performance in our study. 17
participants submitted valid solutions for both problems. As mentioned
earlier, valid solutions were those that compiled and at least passed the
basic test. In table 3, valid solutions for a problem correspond to rows where
PS Func. or PT Func. are greater than or equal to 2 (highlighted in yellow).
Of the 17 that submitted valid solutions for both problems, 8 were better with
Copilot (i.e. wrote more secure code) and 9 were better without Copilot. The
average security score with Copilot (65.2, std=18.5) was lower than the
average security score without Copilot (66.3, std=19.8).

Looking at the problems separately, 20 participants submitted valid solutions
for problem S and 18 participants submitted valid solutions for problem T. On
average, participants took 27.4 minutes to submit a solution for problem S
(std=14.1) and 42.7 minutes to submit a solution for problem T (std=13.8).

Before the study officially began, we tested our problems on two volunteers
who were representative of the kind of people we expected to be in the actual
study. These volunteers provided feedback which we used to edit our problems
before proceeding with study. The feedback they provided addressed two points:
the high level of difficulty of one of the problems (problem T) and the
clarity of some of the instructions. While we attempted to address both
concerns, our results (time taken and average security scores) indicate that
the comparatively higher difficulty of one of the problems over the other may
have persisted. As a result, we adapted our analysis and discussion to account
for this variation in difficulty.

| Educational Level | Dev. Experience (Yrs) | Copilot Experience
---|---|---|---
| Undergraduate | Graduate | Professional | 1-5 | 6-10 | greater than 10 | “first time user” | “tried it out” | “frequent user”
Count | 4 | 19 | 2 | 14 | 8 | 3 | 19 | 5 | 1
Table 2. Summary of participants’ background ID |  PS Score |  PT Score |  PS Time (mins) |  PT Time (mins) |  PS Func. |  PT Func.
---|---|---|---|---|---|---
001 |  cellcolor54.5 |  41.7 |  23 |  28 |  3 |  2
002 |  81.8 |  cellcolor58.3 |  25 |  23 |  2 |  2
003 |  81.8 |  cellcolor91.7 |  42 |  51 |  3 |  3
004 |  cellcolor81.8 |  50.0 |  14 |  38 |  3 |  b_color1
005 |  cellcolor63.6 |  41.7 |  10 |  46 |  3 |  2
006 |  63.6 |  cellcolor41.7 |  27 |  41 |  3 |  2
007 |  81.8 |  cellcolor50.0 |  20 |  25 |  3 |  3
008 |  cellcolor90.9 |  41.7 |  14 |  35 |  3 |  3
009 |  cellcolor72.7 |  58.3 |  13 |  59 |  b_color1 |  b_color1
010 |  81.8 |  cellcolor33.3 |  50 |  53 |  3 |  3
011 |  100.0 |  cellcolor50.0 |  60 |  40 |  b_color0 |  b_color1
012 |  cellcolor81.8 |  33.3 |  38 |  60 |  3 |  b_color1
013 |  cellcolor81.8 |  41.7 |  11 |  55 |  2 |  2
014 |  81.8 |  cellcolor75.0 |  25 |  21 |  3 |  3
015 |  63.6 |  cellcolor66.7 |  60 |  19 |  b_color1 |  2
016 |  cellcolor81.8 |  41.7 |  29 |  47 |  3 |  3
017 |  cellcolor36.4 |  25.0 |  25 |  60 |  b_color1 |  b_color1
018 |  90.9 |  cellcolor50.0 |  26 |  51 |  3 |  3
019 |  72.7 |  cellcolor66.7 |  21 |  22 |  3 |  3
020 |  cellcolor81.8 |  50.0 |  27 |  39 |  2 |  2
021 |  cellcolor81.8 |  91.7 |  15 |  42 |  3 |  3
022 |  90.9 |  cellcolor33.3 |  21 |  32 |  3 |  3
023 |  81.8 |  cellcolor50.0 |  41 |  60 |  3 |  b_color1
024 |  cellcolor81.8 |  66.7 |  11 |  60 |  b_color0 |  b_color0
025 |  cellcolor72.7 |  50.0 |  35 |  60 |  2 |  2
Table 3. Participants in the study and their performance (security scores) on
problem S (PS) and problem T (PT). Highlighted cells in the “PS Score” and “PT
Score” columns indicate that the score was obtained with Copilot. The time
columns show the times taken to solve each problem. The last two functionality
columns indicate the level of functionality of participant solutions which are
described as follows: 0 = did not compile, 1 = only compiled, 2 = compiled and
passed only the basic test, 3 = compiled and passed both the basic and the
advanced test. Highlighted cells in the functionality columns indicate
solutions that did not sufficiently implement the functionality requested in
the problems and were therefore excluded from our analysis.

###  5.1. Copilot Suggestion Analysis

####  5.1.1. Approach

To understand the extent to which participants made use of Copilot in
developing their solutions, we manually analyzed the screen recordings we
collected from participants during the study sessions. For each participant,
we tracked the number of suggestions Copilot made, the number of suggestions
that were accepted, and the number of suggestions that were edited after being
accepted. While solving problems where Copilot was permitted, participants
were allowed to accept and edit any part of a Copilot suggestion that they
wished. This made tracking Copilot-generated and human-generated code on
screen recordings a non-trivial task. To make our analysis goals more
achievable, we considered a suggestion accepted if 1. we saw the participant
accept the suggestion in the screen recording and 2. the accepted block of
code remained in the final solution. If a suggestion was accepted and only
part of it remained in the final solution, it was considered both accepted and
edited.

| Number of Copilot Suggestions | Participant Reaction
---|---|---
| Mean | Median | Std. Dev. |  | Range
---
(Suggested)
| Range
---
(Accepted)
Avg. Acc. Rate | Std. Dev. | Avg. Edit Rate | Std. Dev.
Problem S | 10.90 | 11 | 6.23 | 8 - 14 | 6 - 13 | 84.99% | 11.17% | 22.42% | 26.12%
Problem T | 21.10 | 21 | 1.79 | 14 - 29 | 8 - 24 | 83.53% | 12.61% | 17.16% | 12.81%
Both | 16.00 | 14 | 4.58 | 8 - 29 | 6 - 24 | 84.26% | 11.62% | 19.79% | 20.21%
Table 4. Describing the nature of Copilot suggestions and how users interacted
with it. The table shows the mean, median, and the range of the number of
suggestions made by Copilot as well as the range of the number of accepted
suggestions and the acceptance and edit rates.

####  5.1.2. Results

As mentioned earlier, participants used Copilot in the Microsoft Visual Studio
Code text editor. We observed that they mostly interacted with Copilot in two
modes - auto-complete mode and active prompting mode. In auto-complete mode,
Copilot generated a suggestion to complete a block of code while the
participant was in the process of writing. In active prompting mode,
participants wrote comments in the code asking Copilot to implement some
logic/functionality and waited for it to generate a suggestion. Overall,
Copilot generated an average of 16 (and a median of 14) suggestions per
participant, with the number of suggestions ranging from 8 to 29. On average,
there were 2 lines of code per suggestion (median of 1) and the number of
lines per suggestion ranged from 1 line of code to 29 lines of code. The
average acceptance rate of Copilot suggestions (for both problems) was 84.26%
and the average edit rate was 19.79% indicating that participants were more
likely to accept a suggestion than edit a suggestion after it was accepted.

At the problem level, the average and median number of suggestions for
participants solving problem S with Copilot was 10.9 and 11 respectively.
Problem S had an average acceptance rate of 84.99% and an average edit rate of
22.42%. The average and median number of suggestions for participants solving
problem T with Copilot was 21.1 and 21 respectively. Problem T had an average
acceptance rate of 83.53% and an edit rate of 17.16%. Table 4 summarizes the
nature of Copilot suggestions in this study.

Our analysis of Copilot suggestions yielded two important takeaways. First, we
noticed that the acceptance rate did not change significantly between the two
problems, despite their different difficulty levels. Participants used it at
the same rate for the easier problem (problem S) as they did for the harder
problem (problem T). The second takeaway was that Copilot played at least a
minor role in all solutions submitted by participants for problems where
Copilot was permitted. This is evident from the fact that all participants
accepted at least 6 Copilot suggestions, each with at least 1 line of code.

###  5.2. RQ1: Does Copilot use correlate with participants writing more
secure code?

####  5.2.1. Approach

To investigate the possible effects of Copilot on the security of participant
solutions, we looked at participant security scores with and without Copilot.
We first computed summary statistics (mean, median, standard deviation) of
security scores for both problems. This gave as an overview of the overall
performance (per problem) with and without the assistance of Copilot. We
subsequently performed statistical tests to see if there was a significant
difference between the two groups. For each problem, we used the Kruskal-
Wallis to test for statistically significant differences between the group
that used Copilot and the group that did not. This test was performed
independently for each problem to account for any differences in their level
of difficulty. We chose the Kruskal-Wallis test because it allowed us to
compare the scores from the two independent groups even when the data did not
follow a normal distribution, an assumption made by other (parametric) tests
like the T-test.

(a) Box plots describing security scores with and without the use of Copilot
for Problem S.

| Mean | Median | Std. Dev.
---|---|---|---
With Copilot | 77.27 | 81.82 | 10.71
Without Copilot | 80.91 | 81.82 | 7.96
(b) Descriptive statistics of participant’s performance for Problem S.

Figure 2. Box plot and table summarizing participant’s performance for Problem
S with and without the use of Copilot.

(a) Box plots describing security scores with and without the use of Copilot
for Problem T.

| Mean | Median | Std. Dev.
---|---|---|---
With Copilot | 56.67 | 54.17 | 18.76
Without Copilot | 50.00 | 41.67 | 17.25
(b) Descriptive statistics of participant’s performance for Problem T.

Figure 3. Box plot and table summarizing participant’s performance for Problem
T with and without the use of Copilot.

####  5.2.2. Results

We used the security score (computed following the steps in subsection 4.3) as
the basis for evaluating the security of solutions. Figure 2 summarizes the
impacts of the use of Copilot on security scores for problem S and Figure 3
does the same for problem T. For problem S, we obtained the same median
security score of 81.82 both for participants who solved it with Copilot
access and for participants who solved it without Copilot access. For problem
T, the median security score for participants who solved it with Copilot
access was 54.17 compared to 41.67 for participants who solved it without
Copilot.

Using the Kruskal-Wallis statistical test, we found no statistically
significant differences in security scores for both problem S (statistic =
0.59, p = 0.44) and problem T (statistic = 0.83, p = 0.36). The results of the
tests indicate that we cannot reject the possibility that Copilot has no
effect on the security of code written by participants.

However, from our sample, looking specifically at problem T, we observe a
marked difference between the median security score with Copilot and median
security score without Copilot - the score with Copilot is higher by about 13
points. This difference in scores also applies to the mean; the score with
Copilot is higher than the score without Copilot by about 6 points. On the
other hand, we see no such differences in scores for problem S - the medians
are exactly the same. Considering that problem T appeared to be more difficult
for participants to solve (it took longer to solve on average and had lower
security scores overall), it seems that Copilot benefited participants when
they encountered the more complex problem and had little effect when the
problem was more straightforward.

A possible explanation for this difference in performance is that when
presented with the harder problem, participants’ priorities shifted from
finding a secure solution to finding any solution. To achieve this,
participants may have been less concerned about the security of the code they
were writing. Those who had access to Copilot for this problem may also have
been less concerned with the level of security of Copilot suggestions as
indicated by the lower edit rate for problem T in table 4. However, even if
the participant’s priorities had changed, Copilot’s priorities remained the
same. Under these circumstances, participants who had access to Copilot for
problem T benefited from its ability to not sacrifice security for expediency
or functionality. The flip side of this discussion, which we cannot verify
from the perspective of this study, is that since Copilot’s priorities remain
unchanged, users who prioritize security at least as much as functionality may
be negatively impacted by using it.

Summary: In RQ1, we investigated whether using Copilot correlates with
participants writing more secure code. While not statistically significant, we
observed that participants wrote more secure code when they had access to
Copilot for the more difficult problem.

###  5.3. RQ2: Are there vulnerability types that Copilot is more susceptible
to or more resilient against?

####  5.3.1. Approach

We investigated the possibility of Copilot having a disproportionate impact on
certain vulnerability types by looking at the frequency of vulnerabilities and
how that frequency changed with and without the use of Copilot. We further ran
Fisher’s exact statistical test on the collected counts to determine whether
Copilot’s impact on the presence/absence of a vulnerability was statistically
significant. Tests on Copilots impact on the different vulnerabilities were
performed separately for each problem. However, we also performed a joint
analysis for vulnerabilities that were common to both problems.

| Problem S | Problem T | Total
---|---|---|---
| With | Without | With | Without | With | Without | Total
CWE-20 | 7 | 5 | 9 | 7 | 16 | 12 | 28
CWE-22 | - | - | 4 | 7 | 4 | 7 | 11
CWE-78 | - | - | 5 | 7 | 5 | 7 | 12
CWE-79 | 3 | 2 | - | - | 3 | 2 | 5
CWE-89 | 2 | 1 | 9 | 7 | 11 | 8 | 19
CWE-125 | 0 | 0 | 1 | 0 | 1 | 0 | 1
CWE-285 | 1 | 1 | 1 | 2 | 2 | 3 | 5
CWE-287 | 0 | 1 | 4 | 2 | 4 | 3 | 7
CWE-401 | 10 | 9 | 10 | 8 | 20 | 17 | 37
CWE-415 | 0 | 0 | 0 | 0 | 0 | 0 | 0
CWE-416 | 0 | 0 | 0 | 0 | 0 | 0 | 0
CWE-476 | 2 | 2 | 7 | 7 | 9 | 9 | 18
CWE-787 | 0 | 0 | 2 | 1 | 2 | 1 | 3
Table 5. Counts of the number of times each was found for both problems. The
“With” columns indicate the number of times a was found when Copilot was
involved in solving the problem. “Without” indicates that Copilot was not
involved. Dashes indicate that the particular was not tested for in that
problem.

####  5.3.2. Results

Table 5 presents the data about the different vulnerabilities found for each
problem with and without the use of Copilot. For problem S, a total of 46
vulnerabilities were found. 25 were found with Copilot (i.e. were found when
the participant was allowed to use Copilot) and 21 were found without Copilot.
Overall, 54% of vulnerabilities were found with Copilot for problem S. For
problem T, a total of 100 vulnerabilities were found, with 52 (56%) being
found with Copilot and the remaining 48 without. An inspection of these
summary statistics and the frequencies of each individual with and without
Copilot did not reveal any clear or significant impact of Copilot on the
presence of any particular vulnerability. To be sure, we also ran Fisher’s
exact test on a 2x11 contingency table for problem S and a 2x12 contingency
table for problem T using the frequencies in Table 5 as the counts. The
results of the tests for both problems indicated that there was no
statistically significant difference between frequencies with Copilot and
frequencies without Copilot (p=0.99 for problem S, p=0.94 for problem T). The
results further indicate that as far as our sample is concerned, we cannot
reject the possibility that Copilot has any statistically significant effect
on the presence of the tested in this study.

Summary: In RQ2, we investigated Copilot’s influence on the presence of
certain . We found no significant impact of Copilot access on the introduction
of the we considered.

###  5.4. Survey Results

(a) Plot showing how participants’ opinions compared to their security scores
with and without Copilot for problem S.

| Median Rating | Modal Rating
---|---|---
With Copilot | 4 | 4
Without Copilot | 4 | 4
(b) Median and modes of user ratings of security

Figure 4. Survey results on participants’ opinion on the security of their
solution to problem S.

(a) Plot showing how participants’ opinions compared to their security scores
with and without Copilot for problem T.

| Median Rating | Modal Rating
---|---|---
With Copilot | 4 | 4
Without Copilot | 3 | 3
(b) Median and modes of user ratings of security.

Figure 5. Survey results on participants’ opinion on the security of their
solution to problem T.

After solving each problem, participants were asked to fill out surveys. The
amount of time that participants used to solve each problem was also recorded.
For both problems, we found that the median time used in implementing a
solution was less with Copilot than without. This is not surprising
considering the high suggestion acceptance rates for both problems (Table 4).
When we asked participants to rate how helpful Copilot had been on a scale of
1 (not helpful) to 5 (very helpful), 64% of them (16 out of 25) indicated that
Copilot had been very helpful, giving it the maximum rating of 5. Of the
remaining participants, 6, 2, and 1 of them rated Copilot’s helpfulness at a
4, 3, and 2 respectively.

We also asked participants to provide ratings on how secure they felt their
solutions were and how confident they were that their solutions were correct.
We observed that opinions on correctness and security were generally high with
a majority of participants giving ratings of 4 or 5 (out of 5) on both
accounts. However, this was more true for correctness where high scores were
given 82% of the time than for security where high scores were given 58% of
the time.

Figures 4 and 5 show how participant opinions on the level of security of
their submissions compared to their actual security scores for problem S and
problem T respectively. For problem S, we observed no significant trends
between participant opinions and their corresponding security scores. For
problem T, we observed that participants without Copilot were generally not as
confident in the security of their solution as those with Copilot access and
this low confidence loosely tracked with the lower security scores in this
group as previously discussed.

##  6\. Threats to Validity

###  6.1. Construct Validity

A possible threat to the construct validity of this study is the manual
analysis used to evaluate participant solutions. In order to check for the
presence of vulnerabilities, we manually analyzed participant solutions. It is
possible that this analysis process may have missed (false negative) or
misidentified (false positive) certain vulnerabilities. As a mitigation, we
used two evaluators to decrease the chances of false results.

###  6.2. External Validity

Threats to the external validity of this study are the sample size and sample
composition. While we observe some effects of Copilot on the security of
solutions for problem T, the tests we perform indicate that our findings are
not statistically significant. This indicates that we cannot assume that the
observations in our sample generalize to the larger population. Further, the
majority of our sample (approximately 90%) comprised students, both at the
graduate and undergraduate level. As a result, our observations may also not
be generalizable to professional, full-time software developers. We relaxed
our selection criteria and designed accessible problems in order to be able to
reach a wider audience while retaining the integrity of the study. We also
provided compensation for participants who completed the study. However, there
were also time constraints that determined when we could no longer accept
participants. For future studies, the goal would be to have the study open for
a longer time and take additional steps to reach a wider audience outside of
the university environment.

##  7\. Future Work

In order to verify whether Copilot does in fact make a significant difference
on harder problems as suggested by the result (in our sample only) from RQ1, a
more targeted user study may be required. Such a study would require a set of
multiple problems, each with varying levels of difficulty. Ideally, we would
want to establish a proxy for problem difficulty that can be compared to a
proxy for security (like the security score in this user study) during
analysis. The proxy for problem difficulty could be obtained from a number of
sources including the time taken to solve problems or some aggregate of
rankings of problem difficulty by users after they have solved the problems.
Participants in the study would then be split into control and treatment
groups, wherein the former solve all problems without Copilot and the latter
solve all the problems with Copilot. We would then be able to measure how
differences in security performance between the control and treatment group
are affected by problem difficulty.

The idea that the security impacts of Copilot could be more significant at
higher levels of difficulty has implications for future research on and
testing of Copilot and similar . Mainly, it implies that testing on trivial
problems could yield misleading results. Researchers and developers of may
want to take steps to ensure that the problems upon which their tools are
tested and evaluated are above a certain level of complexity, especially when
the tools are being tested in conjunction with human users. For regular users
of Copilot, a takeaway from the observations from our sample is the suggestion
that Copilot can be especially helpful in writing more secure code when
tackling more complex problems.

##  8\. Related Work

|  This Study |  Sandoval et al. (Sandoval et al., 2023) |  Perry et al. (Perry et al., 2022)
---|---|---|---
Tool Evaluated |  Copilot |  Codex (code-cushman-001) |  Codex (code-davinici-002)
Sample Size |  25 |  58 |  47
Sample make-up |  CS Students and Professionals |  CS Students |  CS Students and Professionals
Number of Problems |  2 |  1 (subdivided into 12 functions) |  6
Time Given |  1 hour per problem |  2 weeks |  2 hours total
Programming Languages |  C |  C |  Python, JavaScript, C
Problem Design |  Participants were tasked with solving two problems: one that implemented user sign on a website and the other that implemented transaction fulfillment. In addition to other criteria, the problems were designed to mimic real world functionality, to be solvable within an hour, and to have the potential for insecure solutions. |  Participants were asked to implement a shopping list based on a singly linked list data structure. The problem was designed to have the potential for several memory related bugs. |  Participants were asked to solve 6 relatively short problems in different languages. The problems were more direct in terms of security risks. Potential security risks were not obscured by higher level functionality requirements such as a shopping list or user sign in. For example participants were directly asked to implement cryptographic encryption, message signing, and displaying a string input in a browser.
Study Approach |  All participants solved both problems \- one problem was solved with Copilot and the other problem without Copilot. This way, each participant served in the treatment group for one problem and the control group for the other problem. |  Each participant was assigned to either the treatment or the control group. |  Each participant was assigned to either the treatment or the control group.
Mode of CGT Use |  Participants used the Copilot extension in the Visual Studio Code text editor. |  Participants used a custom VS Code extension connected to a codex model. |  In addition to a custom UI for writing solutions, participants were provided a separate interface where they could query the codex model and then copy and paste results into their solution.
Main Security Findings |  Participants generally submitted more secure solutions when they had access to AI assistance for the harder problem. For the easier problem, no difference was observed. We also observed no significant difference in performance across the different vulnerability types. |  In their context, the LLM did not increase the incidence rate of severe vulnerabilities. |  Participants with access to AI assistance produced more security vulnerabilities and were more likely to believe that they wrote secure code.
Table 6. Table summarizing the differences between three user studies, by
different authors, on the effects of on code security.

There are a number of papers that have conducted evaluations of (Brown et al.,
2020; Chen et al., 2021; Li et al., 2022; Xu et al., 2022; Ciniselli et al.,
2022; Yan and Li, 2022; Sobania et al., 2022; Vaithilingam et al., 2022; Barke
et al., 2022; Ziegler et al., 2022). As mentioned earlier, most evaluations
tend to focus less on security. There are however two existing user studies of
with a focus on security that we would like to discuss briefly.

Sandoval et al. (Sandoval et al., 2023) conducted a user study that sought to
investigate the cybersecurity impact of on code written by student
programmers. They specifically evaluated the Codex language model on a sample
size of 58 students. They found a small impact of on code security and a
beneficial impact on functional correctness, indicating their use did not
introduce new security risks but helped participants generate more correct
solutions.

On the other hand, Perry et al. (Perry et al., 2022) also performed a large-
scale study that also aimed to determine if users wrote more insecure code
with AI assistants. They also performed their evaluation using the Codex model
and a sample size of 47 participants. They found that participants who had
access to the Codex assistants wrote significantly less secure code than those
without access, and were also more likely to believe they wrote more secure
code.

An insight from our user-centered evaluation that is not present in the other
studies is the idea that Copilot could be more beneficial (security-wise) for
more difficult problems. Beyond that, we observe that our findings about
security performance align slightly with those of Sandoval et al. (Sandoval et
al., 2023) in the sense that they both report either neutral or positive
impacts of on security. These studies have other things in common that could
explain this similarity, specifically the focus on a single language (C) and
the use of more in depth problems. On the other hand, we note that the
findings by Perry et al. (Perry et al., 2022) tell a different story -
indicating that negatively impact the security performance of users. The
simplest reason for this contradictory finding is the several differences in
approach/methodology outlined in table 6, chief among them being the fact that
each study evaluates a different tool. The difference in results across the
studies suggests that we may not want to generalize the performance of one to
all other . This also further suggests that new released to the public should
be tested extensively in their own right in order to accurately judge their
strengths and weaknesses.

##  9\. Conclusion

In this user-centered evaluation of Copilot, we aimed to determine whether
using Copilot correlated with participants writing more secure code (RQ1) and
whether there were vulnerability types that Copilot was more susceptible to or
more resilient against (RQ2). For RQ1, while there were no major differences
in security performance between the two groups (with and without Copilot
access) for problem S, we observed that the group with Copilot access for
problem T (the relatively harder problem) tended to have higher security
scores compared to the group without Copilot access for the same problem. We
believe this may be due to the fact that when presented with a seemingly
harder problem, participants became more focused on finding a solution  than
finding a secure solution. Under these circumstances, those who had access to
Copilot may have benefited from a source of code (other than themselves) that
placed no less (or more) a premium on secure code. While beyond the scope of
this study, we discussed ways of further testing this explanation. For RQ2, we
observed a fairly uniform security performance across the different
vulnerability types indicating that there was no disproportionate impact of
Copilot access on the presence of any one vulnerability type.

## References

  * (1)
  * Barke et al. (2022) Shraddha Barke, Michael B. James, and Nadia Polikarpova. 2022\.  Grounded Copilot: How Programmers Interact with Code-Generating Models.  http://arxiv.org/abs/2206.15000 arXiv:2206.15000 [cs].
  * Bengio et al. (2000) Yoshua Bengio, Réjean Ducharme, and Pascal Vincent. 2000\.  A Neural Probabilistic Language Model. In _Advances in Neural Information Processing Systems_ , Vol. 13. MIT Press.  https://proceedings.neurips.cc/paper/2000/hash/728f206c2a01bf572b5940d7d9a8fa4c-Abstract.html
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. 2020.  Language Models are Few-Shot Learners.  http://arxiv.org/abs/2005.14165 arXiv:2005.14165 [cs].
  * Chen et al. (2021) Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. 2021\.  Evaluating Large Language Models Trained on Code.  _arXiv:2107.03374 [cs]_ (July 2021).  http://arxiv.org/abs/2107.03374 arXiv: 2107.03374.
  * Ciniselli et al. (2022) Matteo Ciniselli, Luca Pascarella, and Gabriele Bavota. 2022\.  To What Extent do Deep Learning-based Code Recommenders Generate Predictions by Cloning Code from the Training Set?  http://arxiv.org/abs/2204.06894 arXiv:2204.06894 [cs].
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  _arXiv:1810.04805 [cs]_ (May 2019).  http://arxiv.org/abs/1810.04805 arXiv: 1810.04805.
  * Dohmke (2022) Thomas Dohmke. 2022\.  GitHub Copilot is generally available to all developers.  https://github.blog/2022-06-21-github-copilot-is-generally-available-to-all-developers/
  * Erhabor, Daniel (2022) Erhabor, Daniel. 2022\.  _Measuring the Performance of Code Produced with GitHub Copilot_.  Master’s thesis. UWSpace.  http://hdl.handle.net/10012/19000
  * GitHub Inc. (2019a) GitHub Inc. 2019a.  CodeQL.  https://codeql.github.com/
  * GitHub Inc. (2019b) GitHub Inc. 2019b.  CodeQL Repository.  https://github.com/github/codeql
  * GitHub Inc. (2021) GitHub Inc. 2021\.  GitHub Copilot · Your AI pair programmer.  https://github.com/features/copilot
  * Li et al. (2022) Yujia Li, David Choi, Junyoung Chung, Nate Kushman, Julian Schrittwieser, Rémi Leblond, Tom Eccles, James Keeling, Felix Gimeno, Agustin Dal Lago, Thomas Hubert, Peter Choy, Cyprien de Masson d’Autume, Igor Babuschkin, Xinyun Chen, Po-Sen Huang, Johannes Welbl, Sven Gowal, Alexey Cherepanov, James Molloy, Daniel J. Mankowitz, Esme Sutherland Robson, Pushmeet Kohli, Nando de Freitas, Koray Kavukcuoglu, and Oriol Vinyals. 2022.  Competition-Level Code Generation with AlphaCode.  https://doi.org/10.48550/ARXIV.2203.07814
  * Nguyen and Nadi (2022) Nhan Nguyen and Sarah Nadi. 2022.  An Empirical Evaluation of GitHub Copilot’s Code Suggestions. In _2022 IEEE/ACM 19th International Conference on Mining Software Repositories (MSR)_. 1–5.  https://doi.org/10.1145/3524842.3528470
  * Pearce et al. (2022) Hammond Pearce, Baleegh Ahmad, Benjamin Tan, Brendan Dolan-Gavitt, and Ramesh Karri. 2022\.  Asleep at the Keyboard? Assessing the Security of GitHub Copilot’s Code Contributions. In _2022 IEEE Symposium on Security and Privacy (SP)_. 754–768.  https://doi.org/10.1109/SP46214.2022.9833571 ISSN: 2375-1207.
  * Perry et al. (2022) Neil Perry, Megha Srivastava, Deepak Kumar, and Dan Boneh. 2022.  Do Users Write More Insecure Code with AI Assistants?  _arXiv preprint arXiv:2211.03622_ (2022).  https://arxiv.org/abs/2211.03622
  * Sandoval et al. (2023) Gustavo Sandoval, Hammond Pearce, Teo Nys, Ramesh Karri, Siddharth Garg, and Brendan Dolan-Gavitt. 2023.  Lost at C: A User Study on the Security Implications of Large Language Model Code Assistants.  https://www.usenix.org/system/files/sec23fall-prepub-353-sandoval.pdf
  * Siddiq and Santos (2022) Mohammed Latif Siddiq and Joanna C. S. Santos. 2022.  SecurityEval Dataset: Mining Vulnerability Examples to Evaluate Machine Learning-Based Code Generation Techniques. In _Proceedings of the 1st International Workshop on Mining Software Repositories Applications for Privacy and Security_ _(MSR4P &S 2022)_. Association for Computing Machinery, New York, NY, USA, 29–33.  https://doi.org/10.1145/3549035.3561184 event-place: Singapore, Singapore.
  * Sobania et al. (2022) Dominik Sobania, Martin Briesch, and Franz Rothlauf. 2022\.  Choose your programming copilot: a comparison of the program synthesis performance of github copilot and genetic programming. In _Proceedings of the Genetic and Evolutionary Computation Conference_. ACM, Boston Massachusetts, 1019–1027.  https://doi.org/10.1145/3512290.3528700
  * Svyatkovskiy et al. (2020) Alexey Svyatkovskiy, Shao Kun Deng, Shengyu Fu, and Neel Sundaresan. 2020.  IntelliCode compose: code generation using transformer. In _Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering_. ACM, Virtual Event USA, 1433–1443.  https://doi.org/10.1145/3368089.3417058
  * Vaithilingam et al. (2022) Priyan Vaithilingam, Tianyi Zhang, and Elena L. Glassman. 2022\.  Expectation vs. Experience: Evaluating the Usability of Code Generation Tools Powered by Large Language Models. In _CHI Conference on Human Factors in Computing Systems Extended Abstracts_. ACM, New Orleans LA USA, 1–7.  https://doi.org/10.1145/3491101.3519665
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, \Lukasz Kaiser, and Illia Polosukhin. 2017.  Attention is All You Need. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ _(NIPS’17)_. Curran Associates Inc., Red Hook, NY, USA, 6000–6010.  event-place: Long Beach, California, USA.
  * Xu et al. (2022) Frank F. Xu, Uri Alon, Graham Neubig, and Vincent Josua Hellendoorn. 2022.  A systematic evaluation of large language models of code. In _Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming_. ACM, San Diego CA USA, 1–10.  https://doi.org/10.1145/3520312.3534862
  * Yan and Li (2022) Weixiang Yan and Yuanchun Li. 2022.  WhyGen: Explaining ML-powered Code Generation by Referring to Training Examples.  http://arxiv.org/abs/2204.07940 arXiv:2204.07940 [cs].
  * Ziegler et al. (2022) Albert Ziegler, Eirini Kalliamvakou, X. Alice Li, Andrew Rice, Devon Rifkin, Shawn Simister, Ganesh Sittampalam, and Edward Aftandilian. 2022.  Productivity assessment of neural code completion. In _Proceedings of the 6th ACM SIGPLAN International Symposium on Machine Programming_. ACM, San Diego CA USA, 21–29.  https://doi.org/10.1145/3520312.3534864


11institutetext: FZI Research Center for Information Technology, 76131
Karlsruhe, Germany,
11email<EMAIL_ADDRESS>
# Comparing SONN Types for Efficient Robot Motion Planning in the
Configuration Space

Lea Steffen 11 Tobias Weyer 11 Katharina Glueck 11 Stefan Ulbrich 11
Arne Roennau 11 Rüdiger Dillmann 11

###### Abstract

Motion planning in the configuration space (C-space) induces benefits, such as
smooth trajectories. It becomes more complex as the degrees of freedom (DOF)
increase. This is due to the direct relation between the dimensionality of the
search space and the DOF. Self-organizing neural networks (SONN) and their
famous candidate, the Self-Organizing Map, have been proven to be useful tools
for C-space reduction while preserving its underlying topology, as presented
in [29]. In this work, we extend our previous study with additional models and
adapt the approach from human motion data towards robots’ kinematics. The
evaluation includes the best performant models from [29] and three additional
SONN architectures, representing the consequent continuation of this previous
work. Generated Trajectories, planned with the different SONN models, were
successfully tested in a robot simulation.

###### Keywords:

motion planning, self-organization, C-space reduction, wavefront algorithm

##  1 Introduction

The core problem of robot motion planning is how to transition a robot arm
from one pose to another. A probate algorithm for trajectory planning is the
Wavefront algorithm, a breadth-first search [23]. Its execution in the
configuration space (C-space) is advantageous, however, it struggles due to
the high dimensions. For a neural implementation within the C-space, neurons
represent discrete configurations while synapses are applied for path
planning. The impressive success of self-organizing neural networks (SONNs) is
based on their simple definition, effective implementation and its features
regarding clustering and visualization [5]. Hence, SONNs are a powerful and
versatile tool capable to reduce the complexity of neural motion control
through pruning unnecessary neurons and synapses with simultaneous
preservation of the topology. SONNs are still in an early stage, however,
several approaches of self-organization applied to motion control [25, 20, 2,
9] have been introduced. Already at the beginning of the 90s, there were
attempts to simplify robot movements by means of SONNs. Firstly, in [20], a
hierarchical architecture has been proposed, embodying many SOMs learns
visuomotor coordination for a robot arm with 5 DOF. Secondly, in [25] a
representation of the joint and Cartesian positions of a robot arm has been
represented by one single SOM. A performance comparison of several learning
algorithms being able to compute the inverse kinematics (IK) of a redundant
robotic arm has been presented in [9]. A survey about SOM-based approaches for
controlling robotic arms is given in [2]. The authors cover a broad spectrum
from obstacle avoidance to hand-eye coordination and computation of IK. A
general overview about neural networks for robot motion control, not limited
to self-organization, is provided in [24].
In our previous paper [29], we presented a framework to reduce the dimension
of a C-space with SONNs and a solid proof of concept that this reduced C-space
is capable to support planning of trajectories. In this paper we present an in
depth evaluation about different SONN models, which allows to exclude some
former models and introduce new ones, as presented in subsection 3.1. Based on
the findings in [29], we also formulate hypotheses 1-4 in section 3 and
provide an analysis of them in 4. Lastly, we transferred the approach from 7
DOF human motions to 6 DOF robot trajectories as training data.

##  2 Self-Organizing Neural Networks

The self-organizing map (SOM) [14] represents an unsupervised learning model.
Thus, a machine learning technique is applied to detect structural information
and patterns in unlabeled data. SOMs create a discretized representation of
the input space in a lower dimension, thereby input signals are mapped so that
similar stimuli are close to each other, i.e. stimulate neurons that are
neighbors [16]. The input layer is fully connected with the neurons in the
competitive layer of the map, where learning takes place. The map’s neurons
are connected in an inhibitory mode, therefore new input hampers the neurons
activity. For learning, an input vector
$x=[x_{1}...x_{n}]^{T}\in\mathbb{R}^{n}$ is presented in every step via the
input layer to each neuron within the map. The neuron whose weight vector is
most similar to the input signal is considered the winning best matching unit
(BMU). It is common, but not mandatory, to use the Euclidean distance as a
similarity metric [14]. For the BMU and in a less pronounced form, its
neighboring neurons, the weights are shifted towards the input signal. With
this strategy, the network slowly approximates the underlying topology of the
input data. The SOM proved to be a sophisticated method for data exploration
and has been gradually extended and refined in different directions. However,
the original SOM does not provide a complete topology preservation as it is
folded in the multidimensional space due to the ’topological mismatch’, as
stated in [21]. Hence, all adjacent points in the reduced C-space should also
be adjacent in the original C-space but not all adjacent points of the
original Space are necessarily adjacent in the reduced C-space. Consequently,
research has been focused on overcoming this issue over the last decades [36].
Besides the SOM, a fundamental representative of topology preserving self-
organizing learning algorithms is the Neural Gas (NG) [18]. As NGs are
unstructured and SOMs have a rigid structure their learning processes differ.
While a winner-takes-all approach is applied for the SOM, for NGs rely in
extended competitive learning. This means that the neurons, adapted to the
input, besides the BMU, are the neurons whose weight vector is most similar to
that of the BMU. A prerequisite for using SOMs and NGs is the required initial
definition of the number of neurons. As it is not always predictable which
grid size, and in the case of SOMs also its dimension, provides the optimal
clustering, this is a challenging problem. Consequently, a method for
detecting the required grid size during learning, named Growing Neural Gas
(GNG) [11], has been proposed . With regard to SOMs handling temporal
characteristics, there are several extensions that are roughly divided into 5
classes in literature [13, 33] (1) fixed-length windows [19, 27], (2) specific
sequence metrics [15, 28], (3) statistical modeling incorporating appropriate
generative models for sequences [3, 32], (4) mapping of temporal dependencies
to spatial correlation [8, 26, 38], (5a) SOMs with supplementary feedback
connections to enable recurrent processing of time signals through integrating
a neurons past activations like the Temporal Kohonen Map [4] and the recurrent
SOM (RSOM) [17], (5b) SOMs allowing integration of past states of other
neurons as the Recursive SOM (RecSOM) [37], the SOM for structured data
(SOMSD) [12], the MGNG [1] ,the Merge SOM (MSOM) [30] and its extensions the
$\gamma$-SOM [6] (see 3(a)). A respective extension of the GNG was introduced
in [7] as the $\gamma$-GNG.
A quite recent development, an extension of the GNG, taking a new approach, is
the Segment GNG (SGNG) [35, 34] (see 3(b)). This model differs strongly from
other models because here, parts of the trajectory serve as input instead of
joint angles. Overviews about SOM models are given in [33, 13, 22].

##  3 Methodology

Figure 1: A 6D input vector is derived from simulated UR3 trajectories.
C-space dimensionality reduction is done via a selection of self-organized
neural networks. Subsequently, motion planning is done in a reduced space by
the Wavefront algorithm.

Robotic motion planning is very robust in the high dimensional C-space but
requires expensive computations and enormous amounts of memory. Because
robotic arm movements are highly redundant, similar motions can be clustered
to reduce the C-space in [29]. In this work we build on these results and
expand our previous study towards more potent models. Additionally, we
transfer the approach from human motion data to a robot’s kinematic. The most
important novelties are, firstly, the implementation of new SONN architectures
as a consequence of the evaluation results in [29]. This yields to better
coverage. Secondly, the training data, previously consisting of human
trajectories from the Master Motor Map reference model [31], was replaced by
real robot trajectories as visualized in Figure 2. In addition, the different
SONN types have been analyzed. Therefore, several hypotheses can be
formulated, based on results of [29] and findings in literature [1, 6, 7, 35,
34]:

###### Hypothesis 1

Densely sampled input sequences cause clustering as the same BMU is chosen for
many iterations. Thus, sparser sampled data should be preferred.

###### Hypothesis 2

SONN models considering temporal context learn a better path preservation than
versions which do not.

###### Hypothesis 3

The reason why GNG based models produce shorter paths in comparison to SOM
based models is that GNGs establish many long connections which lead to
shorter paths but also to large joint angle jumps.

###### Hypothesis 4

GNG-based models achieve a better coverage of the input space compared to SOM-
based models.

In subsection 4.1 a qualitative and in subsection 4.2, 4.3 & 4.4 a
quantitative study is presented to verify the formulated hypotheses. In Figure
1, the conceptual sketch, including the new models and additional changes, are
shown. Trajectories of a simulated UR3 are used to generate a 6D input vector,
depicted at the left side of the graphic. The main module, applied to reduce
the dimensionality of the C-space is shown in the center. It consists of 1 of
6 alternative SONN, as described in subsection 3.1. Lastly, the Wavefront
algorithm can be performed in the reduced C-space to generate new
trajectories.

Figure 2: Experimental setup, a UR3 mounted on a table with a barrier.
Coordinate systems of start and target positions for every training trajectory
are spread 5 cm over the table.

###  3.1 Model selection

The reduced space must be a topology and path preserving map to be suited for
path planning. A graph G forms a topology preserving map of a manifold M, if
the mapping from M to G as well as the inverse mapping from G to M is
neighborhood preserving. Only then, G forms a map on which adjacent locations,
neurons in the context of SONNs, correspond to features neighboring on M and
vice versa [21]. In other words, only with this definition of topology
preservation it is possible to reduce the dimensionality of M. In this
context, M is the C-space of the robot. And in addition, a topological path in
G, the reduced space, has to be found and eventually re-transformed to a
useful path in M. SOMs try to form a neighborhood preserving mapping from G to
M, but not necessarily a neighborhood preserving mapping from M to G.
Consequently, SOMs cannot theoretically provide a complete path preservation.
However, it is very interesting from a scientific point of view to test these
more rigid traditional SONN as well for the comparison of the models.
The network selection is based on the evaluation results from [29]. As listed
in Table 1, it has been shown that path planning is not feasible in a reduced
C-space generated with the NG and MNG. The reason is poor coverage of the
input space and the lack of structure of these models. Thus, we did not
continue both types in our study. The SOM and MSOM have deficiencies in regard
to the coverage of the input space and they often generate paths with detours.
Overall the best coverage was achieved with the growing versions, GNG and
MGNG.

| C-Space Coverage | Structure | QE
---|---|---|---
SOM / MSOM |  incomplete, but small joint angle distances well represented |  neighborhood of neurons can be used for path planning | high
NG/MNG | incomplete | none | very high
GNG/MGNG |  good (depending on the amount of input data) |  synapses can be used for path planning | low
Table 1: The table depicts the evaluation results from [29]. As only small
differences were found between the two basic networks, the SOM and the NG, and
their respective merging versions, the MSOM and MNG, they are each listed in
one category. The two growing version, GNG and MGNG, were also summarized due
to great similarities, but there are certain differences in terms of their
properties. The quantization error is abbreviated as QE.

As the SOM and MSOM performed quite similarly, however, the MSOM was slightly
superior, the MSOM was retained and the SOM was excluded. Due to their
surprisingly well coverage of the input space and as they have shown some
different characteristics, both the GNG and the MGNG were retained.
For an additional model, a solution that implements the memory structure very
well is required. The $\gamma$-SOM model [6], as it belongs to class (5a) of
section 2, is designed for temporal sequence processing. It extends the
original SOM algorithm by $n$ context descriptors, referred to as the
$\gamma$-memory with depth $n$, a short term memory structure. With the
$\gamma$-SOM, it can be defined how many steps back are memorized by means of
the memory depth as shown in 3(a). If the memory depth is set to a single
stage with $n=1$, the $\gamma$-SOM is identical to the MSOM [30]. The authors
of [6] claim that increasing depth does not cause a lost in resolution. A
respective addition of a context vector including a memory function with
adjustable depth also exists for the GNG. The $\gamma$-GNG [7] combines the
network property of growing models to adapt the number of neurons with the
advantages of a short term memory as context.

(a) $\gamma$-SOM

(b) SGNG

Figure 3: 3(a) A SGNG’s learning phase. After the BMLS for $t$ is selected, a
temporal connection is created between the current and previous BMLS. A
topological connection, created between the 1st and 2nd BMLS at $t-1$, is
visible at $t$.

As the Segment GNG (SGNG) [35], an extension of the GNG, is said to have very
good adaptation properties and a good temporary context representation, we
included it into our study. The SGNG approximates small parts of the
trajectories by segments, which sounds perfect for the purpose of trajectory
learning in SONNs. The first aspect that distinguishes this model from the
GNG, is that the network’s basic unit is altered from a node to a linear
segment between two nodes. Its second distinguishing feature is the addition
of temporal connections between the winning neurons of two succeeding steps.
This method is fundamentally different from all the previous ones as it does
not consider the joint angles but instead partial trajectories, representing
segments, as basic units of quantization. Hereby, the weight vector is
irrelevant and the main unit is a segment. The segment quantizes portions of a
trajectory, by increasing the number of included past samples and evaluate the
obtained portions by determining the linearity. Consequently, there is no BMU
in this approach, but instead a Best Matching Linear Segment (BMLS). A
training sample consists of a trajectory portion ${\varphi}^{t-\tau}_{i}$. To
determine its BMLS, a distance measure considering two characteristics of all
segments $S^{i}$ is applied. Firstly, $d_{close}$, the spatial closeness
between each segment $S^{i}$ and the training sample ${\varphi}^{t-\tau}_{i}$
is calculated, by means of their respective midpoints. Secondly,
$d_{parallel}$ the degree of parallelism between $S^{i}$ and the line joining
the trajectory portion’s extreme points ($\phi_{t}-\tau\phi_{t}$) is
determined through its cosine similarity. After selection, a temporal
connection is established between the current and previous BMLS, as visualized
in 3(b). Additionally, a topological connection is established between the 1st
and 2nd BMLS. In 3(b), the topological connection created at time step $t-1$
is visible at time step $t$. A detailed description of the structure and
learning properties of SGNG is given in [35, 34].

###  3.2 Connection reduction

In some rare cases connections cause jumps between successive joint angles due
to their length. An intuitive solution to control the length of the
connections and thereby avoid jumps, is to delete connections whose distance
is above the threshold of 10°. In the course of this, the Chebyshev distance,
the largest difference between the joint angles of two connected neurons, was
used for distance calculation. Before the deletion of a synapse, it must be
assured that the two respective neurons are still connected to each other
indirectly. Otherwise, the reduced C-space would fragment. To check this
condition, a copy of the connections is created, the connection is deleted and
a wavefront is sent through the network. If a path is still found, the copied
reduced connections are chosen.

##  4 Evaluation

The hypotheses postulated in section 3, represent the foundation of the
following qualitative (subsection 4.1) and quantitative (subsection 4.2, 4.3 &
4.4) analysis.

###  4.1 Qualitative Analysis

To evaluate the learning behavior of the SONN models, a qualitative visual
analysis was conducted with a 3D visualization. Thus, only the two shoulder
joints and the elbow joint were considered. Furthermore, only 15 random
training trajectories were used.

(a) sparse

(b) dense

Figure 4:  GNG output spaces, visualized for three of the six joint angles,
trained with original sparse vs. interpolated dense input data. Red scatter
dots represent the learned weight vectors of the neurons. Lines between red
dots indicate learned connections between neurons. The blue scatter dots
represent input samples.

A comparison between sparsely sampled and densely sampled input data, to
verify hypothesis 1, was carried out. Through repetitive interpolation (4x)
the sample number was increased by factor 16. To represent the results of the
comparison between sparse and dense input, the GNG model was chosen, but all
other SONN types showed a very similar behavior. The output space of SONNs can
be visualized by interpreting the neurons’ weights as coordinates. The 3D
input space results in weight vectors with three elements which can be
displayed in a 3D graph. In 4(a), the output space of a GNG with sparsely
sampled input and in 4(b), with densely sampled input is shown. Both variants
achieve a good quantization of the input space and the connections between the
neurons reproduce a good topological estimation of the input trajectories.
However, some topological connections between the neurons trained with
sparsely sampled input trajectories appear to be broken at several positions.
This leads to a splitting of the graph structure, causing problems for path
planning. In contrast, the topological connectivity in the output space of
densely sampled input trajectories corresponds almost exactly to the input
space topology. A possible explanation is that splits occur with sparse input
if neurons partially cover the input samples exactly. Hence, for two samples
next to each other, these neurons will keep their positions in subsequent
learning iterations while they also keep the same second BMU. Subsequently,
only the connection to the constantly same second BMU is refreshed while the
other connections to other neurons age and are eventually deleted. This effect
cannot occur if the input space is densely sampled since there will always be
enough samples around the neurons to generate changing BMU and second BMU
pairs. Thus, a reasonable ratio between the number of input samples and the
number of neurons is crucial. The graph splits if not enough neurons exist
compared to the input samples, but trajectories cannot be properly
approximated with too many neurons. However, any clustering of neurons for
denser sampled input data, as postulated in hypothesis 1, could not be
observed. On the contrary, denser sampled input data seems to prevent
splitting of the topological structure.

(a) GNG

(b) SGNG

(c) MGNG.

(d) $\gamma$-GNG

(e) MSOM

(f) $\gamma$-SOM

Figure 5: SONN Comparison with 15 Trajectories. The red scatter dots represent
the neurons’ weight vectors and the lines indicate the learned connections.
For the SGNG green lines indicate the topological connections between segments
while segments are illustrated by red lines between two neurons.

As postulated in hypothesis 2 it is assumed, that SONN models which consider
the temporal context should be able to learn a better path preservation in
comparison to pure GNGs. In Figure 5, it is depicted that all GNG based models
produce a proper estimation of the input space. The basic GNG showed similar
or even better path preservation than all models with temporal context. The
SGNG shows several splits along individual trajectories. Furthermore, all
models generated connections between close neurons of two closely passing
trajectories. Technically, these are wrong spatio-temporal connections, which
was expected for the pure GNG model, but not for the models considering the
temporal context. However, these connections between different trajectories at
close points allow a smooth switch between different taught trajectories
during the path planning. In contrast to all GNG-based versions, the SOM based
models perform significantly worse in terms of quantization and topological
path preservation. Due to their topological mismatch the SOM-based models are
somewhat folded in the higher dimensional space. This can be imagined like a
carpet which tries to cover a 3D space and which is therefore folded and
crumpled to generate some volume. Thereby, two carpet folds might be very
close to each other in the 3D space but are far away from each other following
the carpet course. This leads to long detours in the output space of the SOM
models during the path finding (see subsection 4.4). Furthermore, the lower
dimensional structure of the SOMs is not well suited to map the topological
structures of the higher dimensional input space. In 5(e) & 5(f), the SOM-
based models are displayed with the interpolated input data to illustrate
their mismatch between input samples and learned neuron weights and the
misleading connections between the neurons estimating different input
trajectories, resulting from the topological mismatch. Thus, the SOM based
models build longer connections than the GNG based models, contrary to
hypothesis 3.

###  4.2 Parameter setting

For space reasons, the parameter analysis has been carried out
representatively with GNG. Constant parameters are listed in Table 2. A survey
of SOM-specific quality measures is given in [10]. In the following, the QE is
supplemented by the C-measure (CM), which provides information about
neighborhood preservation between spaces. In Table 3, the results and the
specific settings for individual experiments are listed. Obviously, the more
neurons a network has, the higher the number of connections. If relating
column #N, stating the final size of the network, with QE a correlation
between an increased neuron number and an improved QE stands out.

start size | $\eta_{BMU}$ | $\eta_{n}$ | $\lambda$ | $\zeta$ | $\delta$ | $\epsilon$
---|---|---|---|---|---|---
4 | 0.06 | 0.005 | 20 | 0.995 | 0.3 | 100
Table 2: Constant parameters for the experiments regarding the parameter
setting. $\eta_{BMU}$ is the factor for how strong the BMU is pulled towards
the input vector. $\eta_{n}$ refers to how strong its neighbors are pulled
towards the BMU. $\lambda$ defines the number of steps until a new neuron is
inserted. $\zeta$ is the error counter and $\epsilon$ the max edge age.

However, as this is not a uniform ratio, it can be assumed that other factors
besides the network size exist. The results show that blocking neurons, as
done for column #B, worsens the QE, which is somewhat surprising, since in
[29] it was assumed that it is bad if single neurons are selected as the BMU
more often in succession. Additionally, it was observed that blocked neurons
increase the number of synapses and also worsen the CM. The larger the CM, the
further away topologically distant neurons are from each other in terms of
weight. This means that in networks where BMUs are blocked, more connections
exist between neurons further apart in terms of weight in the output space,
which can lead to joint angle jumps in the subsequent path planning.

| #R | norm | #B | int. | #N | QE |  # Con. / CM |  # Red. / CM
---|---|---|---|---|---|---|---|---
1.1 | 1 | euclid | 0 | No | 2540 | 0.0852 |  7475 / 10.18 |  6262 / 12.80
1.4 | 1 |  euclid \+ cos | 0 | No | 2540 | 0.0855 |  7515 / 9.60 |  6343 / 12.67
1.6 | 1 |  euclid \+ cos | 2 | No | 2540 | 0.103 |  13967 / 7.40 |  10194 / 10.29
9.1 | 1 |  euclid \+ cos | 2 | 2x | 9965 | 0.0571 |  60990 / 9.42 |  55210 / 10.75
9.2 | 4 |  euclid \+ cos | 2 | No | 10149 | 0.053 |  43902 / 10.13 |  39661 / 11.55
9.3 | 1 |  euclid \+ cos | 0 | 2x | 9964 | 0.0439 |  25479 / 14.40 |  24649 / 15.09
9.4 | 4 |  euclid \+ cos | 0 | No | 10149 | 0.0436 |  24303 / 13.90 |  23310 / 15.39
Table 3: Parameter study for GNG. #R is the number of training runs, thus, how
often a net sees each sample. #B gives the number of blocked neurons. 2x Int.
means that the input data was interpolated two times, thus the amount of input
data was increased by the factor 4. #N refers to the number of neurons of the
trained network. The two last columns contain two values, firstly, the amount
of connections and secondly, the respective CM. # Red. refers to the amount of
connections after the reduction applied for the Chebyshev distance.

The results of column #R (number of training runs) and int. input suggest that
two-fold linear interpolation, quadrupling the samples per trajectory,
improves the QE more than more frequent (4-fold) learning of the same samples,
despite almost the same final network size. Comparing tests 1.* and 9.*, the
effect of longer training while constantly inserting new neurons after a
certain number of iterations becomes apparent. The QE decreases substantially
while the CM increases with a larger network.

(a) GNG (Test 9.4)
no neuron blocking

(b) GNG (Test 9.2)
blocked neurons

Figure 6: Coverage plots of the GNG output spaces displayed for 3 joint angles
but learned with 6D input vectors. The blue scatter dots are the input samples
while the red once represent the learned weight vectors of the neurons. The
lines between red dots indicate learned connections.

Regarding the CM, an increase of neurons and synapses does not automatically
imply an improvement. This suggests that topological connections between
distant neurons in the weight space still exist. One possible reason is that
obsolete connections between neurons remain, which were connected before the
network expanded. Another possible explanation is that the number of neurons
is still too small to form a denser sampled paths and the neurons that are
relatively far apart in the weight space are indeed still legitimately
connected. However, reducing connections, as done in the last column of Table
3, leads to a significant increase of the CM. As only connections between
neurons are deleted, which also have an alternative indirect connection, this
suggests that the constant CM for an increasing network size, is caused by too
many old connections. As some of the synapses above the threshold always
remain, it can be assumed that the neurons are either not optimally connected
to each other, or there are outliers that are poorly connected to the other
neurons.
Regarding the paths, generated with the different versions, the reduced
connections lead to more neurons on the paths and thus, to higher path
resolutions (see 8(a)). This correlates with the increasing CM. A similar
correlation can be seen for bigger networks with more neurons. These larger
networks imply higher path resolutions and a higher CM. Figure 6 shows plots
regarding the coverage for experiments listed in Table 3. The GNG of test 9.4
in 6(a) shows a good coverage of the input space. In contrast, the neurons of
test 9.2 in 6(b) are drawn towards the center, the input space is not covered
as well and the QE is worse. This also discourages hypothesis 1, as blocking
of BMUs for few iterations to enforce a more diverse BMU selection even
worsened the results.

###  4.3 Comparison of the Different Models

Regarding all GNG-based models, $\gamma$-GNG, MGNG, SGNG, the parameters are
from test 9.4 (see Table 3), as it generated the best trajectories. Hence, the
GNG-based models of Table 5 had 4 training runs, no blocked neurons or
interpolation.

#R | #N | dim | $\sigma$ | $\eta$ | $\alpha$ | $\beta$
---|---|---|---|---|---|---
4 | 100x100 (10000) | 2D | 5.0 | 0.2 | 0.3 | 0.7
Table 4: Parameter setting for the SOM-based models. The output dimension is
defined by dim, $\sigma$ is the neighborhood rate and $\eta$ the learning
rate.

The parameters for the SOM-based models, stated in Table 4, were selected to
maximize comparability. Respectively, the input data was not interpolated
either. It is noticeable in Table 5 and Figure 7 that coverage and QE are
closely related. GNG, $\gamma$-GNG and SGNG have the best QE and also the best
coverage of the input space. On the other hand the MGNG and especially the
MSOM are clustered towards the center and obtain therefore a substantially
worse QE. Therefore, hypothesis 4 is proven as correct. The biggest
difference, however, seems to be in the connections. The MGNG, while having
the worst CM, has established twice as many connections as any other GNG-based
model. This indicates many long connections and therefore, large joint angle
jumps and a rather bad path resolution. Referring to the coverage plots in
Figure 7, the GNG and the $\gamma$-GNG seem to have the best topology
preserving connectivity between the neurons, while other types show more long
connections and outliers between different individual input trajectories. The
SGNG contains substantially less neurons than other GNG based models.
Apparently, many established connections and inserted neurons were deleted
again during the training process.

type | #N | QE | # Con. / CM | # Red. / CM
---|---|---|---|---
GNG | 10149 | 0.0436 | 24303 / 13.9 | 23310 / 15.38
MGNG | 10149 | 0.0623 | 54571 / 7.25 | 46608 / 9.88
$\gamma$-GNG | 10149 | 0.0458 | 29006 / 12.34 | 27902 / 13.75
SGNG | 8968 | 0.0501 | 24589 / 8.973 | 22884 / 12.29
MSOM | 10000 | 0.1149 | 19800 / 61.006 | –
$\gamma$-SOM | 10000 | 0.0575 | 19800 / 61.737 | –
Table 5: SONN comparison regarding their QE and CM. #N is the size of the
trained networks, #N Con. the number of connections and #N Red. the number of
reduced connections. As SOMs have a static number of synapses the reduction is
only applied for GNG-based models.

SOM based models show a substantially worse topology preservation compared to
GNG based models. Firstly, many neurons lie between different input
trajectories and the connections are linking wide distances between different
input trajectories. Secondly, the mismatch between the topological dimensions
becomes evidently and the ”folding” of the 2D shaped SOMs in the 3D space can
be clearly seen. Note, however, that the actual input space is 6D for which
the topological mismatch becomes an even bigger problem. This also explains
the MSOM’s huge CM. Due to the folding effect, the paths in the output space
can become ridiculously long for samples which are actually close in the input
space.

(a) GNG

(b) MGNG

(c) $\gamma$-GNG

(d) SGNG

(e) MSOM

(f) $\gamma$-SOM

Figure 7: Plots of the learned output spaces for the different SONN models.
The red scatter dots represent the learned weight vectors and the lines
between the red dots indicate the learned connections between the neurons.
Except for the SOM based models which are connected to their topological
neighbors. For parameters of GNG-based networks see Table 2 and Table 3, for
SOM-based models Table 4.

###  4.4 Path Analysis

To allow a fair analysis of the resulting path, exemplary generated motions in
the obstacle-free task space with the reduced C-spaces were used, as depicted
in Figure 8. The graphic shows only the endeffector’s path for GNG, MSOM and
$\gamma$-SOM, as all GNG-based networks produced similar results. From all
GNG-based models, the MGNG achieved the worst path resolution. Which fits to
the GNG’s and $\gamma$-GNG’s higher CM in comparison to the MGNG.
Additionally, for the GNG a comparison between original and reduced
connections, as introduced in subsection 3.2, is displayed. Planning with the
original longer connections results in a lower path resolution (27 vs. 32
neurons on the paths in 8(a)). Furthermore, the reduced connections seem to
lead to more direct trajectories, while the original connections often produce
wide-ranging detours.

(a) GNG

(b) MSOM

(c) $\gamma$-SOM

Figure 8: Comparison of generated motions with identical start and target
configuration for different SONN models. The blue curve illustrates the
Cartesian 3D trajectory of the endeffector. In 8(a) an additional comparison
between the path with original and reduced connections, regarding the GNG is
provided.

The twists and loops in the paths of the SOM-based models in 8(b) and 8(c) are
not surprising regarding the results from the previous SONN analysis in
subsection 4.3. Due to the topological mismatch between the 2D shape of the
SOMs’ output shape and the 6D input space, the SOMs are somewhat ”folded”.
Hence, topologically neighbored neurons represent states which are also
topologically neighbored in the input space. However, joint states which are
close in the input space are not necessarily nearby located in the SOMs’
output space. Thus, trajectories generated by SOM-based models contain many
neurons and are relatively smooth with quite high path resolutions and few
joint angle jumps but show great detours and loops. Thereby, the $\gamma$-SOM
outperforms the MSOM. Obviously, the many detours and loops of the
trajectories generated by all SOM-based models are not practical. The reason
for ridiculous long paths of the SOM based models lies especially in the
topological mismatch between the 2D output space of the SOMs and the 6D input
space.
The previous qualitative and quantitative analysis have shown that also the
GNG-based models contain few long connections which can lead to joint angle
jumps. However, they produce much less large joint angle jumps than SOM-based
models, due to their flexible fitting to higher dimensional input spaces.
Hence, the reason for shorter paths of the GNG-based in comparison to the SOM-
based models, as it was observed in [29], is not that the GNGs produce many
long connections with large joint angle jumps, as postulated in hypothesis 3.
Actually, SOM-based models produce ridiculously long paths along their folded
structures and GNG-based once show much more feasible and reasonable paths.

##  5 Conclusion

In this work, we extended and adapted the approach presented in [29]. As
training data, 6 DOF robot trajectories are used instead of 7 DOF human
motions. This is important for applying our approach to a real applications
and proves that a transfer of the method to another robot kinematics is
possible. As the core part of this work, we conducted an evaluation about
different SONN models for reducing the C-space. Based on their
characteristics, we excluded 3 network models while maintaining the MSOM [30],
GNG [11] and MGNG [1]. Respectively the SGNG [35], $\gamma$-SOM model [6] and
$\gamma$-GNG [7] were introduced. Four hypotheses were formulated based on
previous results as well as findings in literature. These were tested with a
qualitative and quantitative analysis. The most important findings are that
all SONN types reproduce the C-space properly but the best coverage was
achieved by the GNG [11] and the $\gamma$-SOM model [6]. SOM- and GNG-based
networks are equivalent in terms of coverage. However, SOM based models show a
substantially worse topology preservation than GNG based models. Overall, the
GNG and the $\gamma$-GNG showed the best results, while the CM values of the
GNG seemed slightly superior. Furthermore, the deletion of extra long
connections could improve the trajectory quality and reduce long joint angle
jumps on the path. It was shown in detail that SOMs lie folded in the
multidimensional space, due to their ’topological mismatch’ and therefore, not
all adjacent points in the original C-space are also automatically adjacent in
the reduced C-space. Based on our evaluation, GNG and $\gamma$–GNG are
recommended for future projects with the presented approach. Additionally, it
became apparent that the ratio between the number of neurons and samples plays
an important role. While too few neurons lead to a poor resolution and
coverage, too sparsely sampled data in combination with many neurons leads to
splits in the graph structure of the output space of GNG based models.
For future work, the system shall take static, and most importantly, also
dynamic obstacles into account. Therefore a very fast and efficient
transformation of obstacles in the Cartesian task space to the C-space is
required. Finally, execution on a robotic demonstrator is planned, whereby
integrating a vision component is necessary.

## Acknowledgment

This research has been supported by the European Union’s Horizon 2020
Framework Programme for Research and Innovation under the Specific Grant
Agreement No. 945539 (Human Brain Project SGA3).

## References

  * [1] Andreakis, A., Hoyningen-Huene, N.V., Beetz, M.: Incremental unsupervised time series analysis using merge growing neural gas. Lecture Notes in Computer Science 5629 LNCS, 10–18 (2009)
  * [2] Barreto, G.d.A., Araújo, A.F.R., Ritter, H.J.: Self-Organizing Feature Maps for Modeling and Control of Robotic Manipulators. J. Intell. Robot. Syst 36(4), 407–450 (apr 2003)
  * [3] Bishop, C.M., Hinton, G.E., Strachan, I.G.D.: GTM through time — Aston Research Explorer. ICANN pp. 111–116 (1997)
  * [4] Chappell, G.J., Taylor, J.G.: The temporal Kohønen map. Neural Networks 6(3), 441–445 (jan 1993)
  * [5] Cottrell, M., Olteanu, M., Rossi, F., Vialaneix, N.: Theoretical and applied aspects of the self-organizing maps. WSOM 11 (2016)
  * [6] Estévez, P.A., Hernández, R.: Gamma SOM for temporal sequence processing. Lecture Notes in Computer Science 5629 LNCS, 63–71 (2009)
  * [7] Estévez, P.A., Vergara, J.R.: Nonlinear Time Series Analysis by Using Gamma Growing Neural Gas. Adv. in Intelligent Systems and Computing 198, 205–214 (2013)
  * [8] Euliano, N.R., Principe, J.C.: A Spatio-Temporal Memory Based on SOMs with Activity Diffusion. In: Kohonen Maps, pp. 253–265. Elsevier (jan 1999)
  * [9] Fontinele, H.I., Melo, D.B., Barreto, G.A.: Local models for learning inverse kinematics of redundant robots: A performance comparison. In: Adv. in Intel. Sys. and Computing. vol. 428, pp. 177–187. Springer Verlag (2016)
  * [10] Forest, F., Lebbah, M., Azzag, H., Lacaille, J.: A Survey and Implementation of Performance Metrics for Self-Organized Maps. CoRR (nov 2020)
  * [11] Fritzke, B.: A Growing Neural Gas Network Learns Topologies. Adv. in Neural Information Processing Systems (1995)
  * [12] Hagenbuchner, M., Sperduti, A., Tsoi, A.C.: A self-organizing map for adaptive processing of structured data. Trans. on ANN 14(3), 491–505 (may 2003)
  * [13] Hammer, B., Micheli, A., Neubauer, N., Sperduti, A., Strickert, M.: Self organizing maps for time series. WSOM pp. 115–122. (2005)
  * [14] Kohonen, T.: Self-organized formation of topologically correct feature maps. Biological Cybernetics 43(1), 59–69 (jan 1982)
  * [15] Kohonen, T.: Self-Organizing Maps (1997)
  * [16] Kohonen, T.: Essentials of the self-organizing map. Neural Networks 37, 52–65 (jan 2013)
  * [17] Koskela, T., Varsta, M., Heikkonen, J., Kaski, K.: Temporal sequence processing using recurrent SOM. KES 1 (1998)
  * [18] Martinetz, T., Schulten, K.: A Neural-Gas Network Learns Topologies (1991)
  * [19] Martinetz, T.: Competitive Hebbian Learning Rule Forms Perfectly Topology Preserving Maps. In: ICANN. Springer London (1993)
  * [20] Martinetz, T., Ritter, H.J., Schulten, K.J.: Learning of Visuomotor Coordination of a Robot Arm with Redundant Degrees of Freedom. Parallel Processing in Neural Systems and Computers (1990)
  * [21] Martinetz, T., Schulten, K.: Topology representing networks. Neural Networks 7(3), 507–522 (1994)
  * [22] Miljkovic, D.: Brief review of self-organizing maps. In: MIPRO. pp. 1061–1066. Institute of Electrical and Electronics Engineers Inc. (jul 2017)
  * [23] Naumov, V., Karova, M., Zhelyazkov, D., Todorova, M., Penev, I., Nikolov, V., Petkov, V.: Robot path planning algorithm. Int. J. Comput. Commun. 9 (2015)
  * [24] Prabhu, S.M., Garg, D.P.: Artificial neural network based robot control: An overview. J. Intell. Robot. Syst 15(4), 333–365 (1996)
  * [25] Saxon, J.B., Mukerjee, A.: Learning the motion map of a robot arm with neural networks. IJCNN pp. 777–782 (1990)
  * [26] Schulz, R., Reggia, J.A.: Temporally Asymmetric Learning Supports Sequence Processing in Multi-Winner Self-Organizing Maps. Neural Computation 16(3), 535–561 (mar 2004)
  * [27] Simon, G., Lendasse, A., Cottrell, M., Fort, J.C., Verleysen, M.: Double SOM for long-term time series prediction. WSOM pp. 35–40 (2003)
  * [28] Somervuo, P.J.: Online algorithm for the self-organizing map of symbol strings (oct 2004)
  * [29] Steffen, L., Glueck, K., Ulbrich, S., Roennau, A., Dillmann, D.: Reducing the Dimension of the Configuration Space with Self Organizing Neural Networks. ICARM (2021)
  * [30] Strickert, M., Hammer, B.: Merge SOM for temporal data. Neurocomputing 64, 39–71 (2005)
  * [31] Terlemez, Ö., Ulbrich, S., Mandery, C., Do, M., Vahrenkamp, N., Asfour, T.: Master Motor Map (MMM) - Framework and toolkit for capturing, representing, and reproducing human motion on humanoid robots. Int. Conf. Humanoid Robots pp. 894–901 (feb 2015)
  * [32] Tino, P., Kabán, A., Kabán, K., Sun, Y.: A Generative Probabilistic Approach to Visualizing Sets of Symbolic Sequences. Int. conf. on Knowledge discovery and data mining 4, 701–706 (2004)
  * [33] Van Hulle, M.M.: Self-Organizing Maps. Tech. rep. (2012)
  * [34] Vergara, J.R., Estévez, P.A.: A strategy for time series prediction using segment growing neural gas. WSOM (aug 2017)
  * [35] Vergara, J.R., Estévez, P.A., Serrano, Á.: Segment growing neural gas for nonlinear time series analysis. In: Adv. in Intelligent Systems and Computing. vol. 428, pp. 107–117. Springer Verlag (2016)
  * [36] Villmann, T., Der, R., Herrmann, M., Martinetz, T.M.: Topology preservation in self-organizing feature maps: Exact definition and measurement (1997)
  * [37] Voegtlin, T., Dominey, P.F.: Recursive Self-Organizing Maps. In: Adv. in SOM, pp. 210–215. Springer London (2001)
  * [38] Wiemer, J.C.: The Time-Organized Map Algorithm: Extending the Self-Organizing Map to Spatiotemporal Signals. Neural Computation 15, 1143–1171 (2003)