=Paper=
{{Paper
|id=Vol-2806/short4
|storemode=property
|title=Robot Choreographies: Artificial Evolution between Novelty and Similarity
|pdfUrl=https://ceur-ws.org/Vol-2806/short4.pdf
|volume=Vol-2806
|authors=Mattia Barbaresi,Stefano Bernagozzi,Andrea Roli
|dblpUrl=https://dblp.org/rec/conf/aiia/BarbaresiBR20
}}
==Robot Choreographies: Artificial Evolution between Novelty and Similarity==
https://ceur-ws.org/Vol-2806/short4.pdf
Robot choreographies: artificial evolution between
novelty and similarity
Mattia Barbaresia , Stefano Bernagozzia and Andrea Rolia
a
Dipartimento di Informatica - Scienza e Ingegneria, Alma Mater Studiorum Università di Bologna, Campus of Cesena,
Via dell’Università 50, Cesena, Italy
Abstract
In this paper we introduce a novel fitness function for evolutionary art, which generates sequences
of movements—i.e. robot choreographies—based on similarity to an inspiring repertoire. Similarity
is counterbalanced by a novelty mechanisms, which makes it possible to sample unexplored areas of
the choreography space. The approach is discussed together with preliminary results achieved in the
context of Nō theatre. This work is a first step towards the development of a computational creativity
system that can incorporate diverse generative mechanisms and can exploit information theoretic and
complexity measures both for the generation and assessment of the choreographies produced.
Keywords
Computational, Creativity, Evolutionary Art, Robotics, Similarity, Novelty
1. Introduction
Computational creativity (CC) is an emerging field of research within AI that studies the ability
of machines to both generate and evaluate novel outputs that would, if produced by a human,
be deemed creative. Computers and creativity make interesting partners with respect to two
different aims: one is understanding human creativity, the other is trying to produce “machine
creativity”, in which the computer at least appears to be creative, to some degree [1]. In this
context there exists a wide spectrum of activities. Most researchers are focused on specific tasks,
such as the generation of music [2], paintings [3], poetry [4], jokes [5] or games [6]. Some, such
as Wiggins [7] and Ritchie [8], are interested in the generic frameworks within which such
tasks take place, and how to evaluate them.
The majority of these works have been drawn from one of the most computationally tractable
definitions of creativity, which has been proposed by Margaret Boden [9]: creativity is the
ability to come up with ideas or artefacts that are new, surprising, and valuable [1]. So today it
is widely accepted that something to be called creative needs to meet at least two main traits:
novelty (or unexpectedness, unpredictability, surprise, originality) and value (or usefulness,
quality, appropriateness, meaningfulness) [10].
These concepts—and novelty in primis—may find their definition in the context of Information
Theory [11]; the theoretical tools it provides enable one to formalise the crucial concepts of
The 7th Italian Workshop on Artificial Intelligence and Robotics (AIRO 2020)
Envelope-Open mattia.barbaresi@unibo.it (M. Barbaresi); andrea.roli@unibo.it (A. Roli)
Orcid 0000-0003-2684-5311 (M. Barbaresi); 0000-0001-9891-5441 (A. Roli)
© 2020 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
CEUR Workshop Proceedings (CEUR-WS.org)
pattern and randomness that are central to learning and computer capability of generating, and
relevant to evaluating the novelty of new generated products [12].
Our long term objective in CC aims at investigating these fundamental aspects with a two-fold
perspective: exploring mechanisms for the generation of creative artefacts and exploiting infor-
mation theory metrics for the assessment of such systems. Compared to the works mentioned
above, our approach is different and tries to investigate CC on an empirical basis. With these
assumptions, as an interdisciplinary research group, 1 we decided to explore the generation
of robot choreoghraphies for the Nō theatre, a traditional form of classical Japanese musical
drama.
In this work we present the first steps of this research. We conceived a genetic algorithm
(GA) which, starting from a given inspiring repertoire and a set of unitary moves, generates
symbolic sequences of movements (i.e., choreographies) exploiting similarity with the repertoire
combined with the novelty search approach [13].
2. Proposed approach
The idea was to start from a simple, basic system, that includes primitive but essential mecha-
nisms for creative generation (appropriateness/similarity and novelty) then increasingly add
features that enhance the creative potential of the generative system, to evaluate the effects
that these modifications have on the metrics used for the assessment. So we started encoding
similarity and novelty in a genetic algorithm. To do this, we conceive a fitness function that
evaluates the average similarity of an individual from the samples in the inspiring set. The
entire generation process is guided by the novelty search approach described in [13]. These
choreographies are performed by a (virtual) Nao robot 2 using CoppeliaSim 3 environment.
2.1. Encoding
We represent a choreography as a sequence of basic moves (i.e., figures or poses). Each figure is
stored as a single keyframe (motion capture data) that specifies a particular position of each
captured joint and is encoded as a symbol. Therefore, in our representation a choreography is a
sequence of symbols. Hence, the GA generates strings (symbols sequences) that are mapped to
keyframe series (sequences of joint angles sets). The actual movement of the robot is given by
the transition from one keyframe to another. Only steady poses are encoded and we assume
that the transition between stable moves is stable too, taking advantage of the typical gentle
style of Nō movements. This, in general, represents a limitation for robot movements in real
applications (e.g., some moves or transitions could make the robot fall) but runs well for our
purpose.
1
Performing Robots: https://site.unibo.it/performingrobots/en
2
Softbank Robotics: http://doc.aldebaran.com/2-1/home_nao.html
3
Coppelia Robotics: https://www.coppeliarobotics.com
2.2. Inspiring set and similarity
In general—but especially when dealing with artistic problem modelization—it is not trivial to
conceive a (fitness) function that fully captures all the problem objectives. What is valuable?
And how a choreography can be judged as more valuable than another? Note that in this case,
we use the term value as a synonym of appropriateness or membership. The value, the quality,
of an artefact will usually be assessed by other agents’ (humans) judgement and will be based
on cultural experience and knowledge, and hence are likely to reflect historical comparisons of
the artefacts. These aspects refer more to the H-creativity [9] and will be addressed in future
work. To model this aspect in this first attempt, the idea is to take a sample repertoire and to
evaluate each individual through its similarity with respect to such a given set. The inspiring
set represents choreographies that the robot, or the dancer, knows about a particular style or
repertoire, which is the knowledge from which the artist pursues its style and creates new
pieces. As a first step, we created the repertoire by manually encoding typical sequences of
moves (kata) that have been performed by a Nō expert.4
Therefore, the fitness function evaluates sequences using string similarity between individuals
and this repertoire. In formulas:
𝑐𝑎𝑟𝑑
1
𝑓 𝑖𝑡𝑛𝑒𝑠𝑠(𝑥) = ∑ 𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑡𝑦(𝑟𝑒𝑝𝑒𝑟𝑡𝑜𝑖𝑟𝑒[𝑛], 𝑥) (1)
𝑐𝑎𝑟𝑑 𝑛=1
𝐽 𝑊 (𝑥, 𝑦) + 𝐽 𝑎𝑐𝑐(𝑥, 𝑦)
𝑠𝑖𝑚𝑖𝑙𝑎𝑟𝑖𝑡𝑦(𝑥, 𝑦) = 1 − (2)
2
where 𝑐𝑎𝑟𝑑 = |𝑟𝑒𝑝𝑒𝑟𝑡𝑜𝑖𝑟𝑒| is the cardinality of the repertoire (i.e., the number of sequences forming
the repertoire), 𝑟𝑒𝑝𝑒𝑟𝑡𝑜𝑖𝑟𝑒[𝑛] is the 𝑛th element of that inspiring set and where the similarity is
formulated as the combination of Jaro-Winkler and Jaccard [14] string distances, respectively
𝐽 𝑊 (𝑥, 𝑦) and 𝐽 𝑎𝑐𝑐(𝑥, 𝑦) in equation 2. Similarity can be thought of as the convergent process
in the generation that constrains the resemblance of generated artefact to given samples.
2.3. Novelty search
Convergent/divergent thinking is a characteristic of creativity; to model these dynamics, we
include a novelty search mechanism that guides the generation in the opposite way with respect
to similarity. The novelty mechanism is inspired by the work of Vinhas et al. [13]. The main
goal of this algorithm is to generate a more diverse set of individuals than the set that would be
created by a traditional fitness based evolutionary algorithm. The method evolves individuals
according to two criteria: (i) look for the best individuals according to the fitness function
and (ii) take novelty and fitness as two different objectives to be maximised using a Pareto
optimization. This bi-objective optimization is performed considering the number of individuals
of the current generation that have a fitness above a given threshold. It uses also an archive to
store the most novel individuals. The novelty score is then calculated as
𝑘
1
𝑛𝑜𝑣𝑒𝑙𝑡𝑦(𝑥) = ∑ 𝑑𝑖𝑠𝑠𝑖𝑚(𝑥, 𝑗) (3)
𝑘 𝑗=1
4
https://site.unibo.it/performingrobots/en/project/activities
where 𝑑𝑖𝑠𝑠𝑖𝑚(𝑥, 𝑗) is a dissimilarity metric, between the individual being evaluated and a set of
𝑘 neighbours chosen from the population and the archive. We implemented the dissimilarity
metric by complementing the similarity function.
2.4. Results
We tested the algorithm by varying several parameters, among which the size of the repertoire,
and we compared the results of the combined use of similarity and novelty with simple fitness-
based GA results and random search—which may represent a naive way of producing a divergent
process. For lack of space, here we just briefly summarize the main results. As expected, the
overall similarity slightly decreases with the size of the repertoire, meaning that the search
process achieves a similarity balance between the generated individuals and the ones in the
repertoire. The drift imposed by novelty turns out to be effective, as the best choreographies
generated are usually sensibly different among themselves, considerably more diverse than
those generated at random. Some samples of the choreographies can be found here: https:
//github.com/ste93/NaoNohVideos.
3. Ongoing and future work
Currently we are performing a quantitative assessment of the choreographies by applying in-
formation theory and complexity measures. These metrics make it possible to capture relevant
features of the choreographies that can be used both for identifying their peculiarities and dif-
ferences (and possibly compare the fingerprint provided by the metrics with human evaluation),
and derive some heuristics for improving the generation process. This approach is analogous
to that recently proposed for swarm robotics [15]. Among the metrics that we are currently
applying we mention the Normalized Compression Distance [16]—which is an alternative to
similarity and it is based on Kolmogorov complexity—and the Set-based Complexity [17], which
is aimed at reckoning the heterogeneity of an ensemble of non-random strings.
References
[1] M. A. Boden, Creativity in a nutshell, Think 5 (2007) 83–96.
[2] J. Biles, et al., Genjam: A genetic algorithm for generating jazz solos, in: ICMC, volume 94,
1994, pp. 131–137.
[3] P. McCorduck, Aaron’s code: meta-art, artificial intelligence, and the work of Harold
Cohen, Macmillan, 1991.
[4] P. Gervás, Computational approaches to storytelling and creativity, AI Magazine 30 (2009)
49–49.
[5] G. Ritchie, R. Manurung, H. Pain, A. Waller, R. Black, D. O’Mara, A practical application
of computational humour, in: Proceedings of the 4th International Joint Conference on
Computational Creativity, 2007, pp. 91–98.
[6] A. Liapis, G. N. Yannakakis, J. Togelius, Computational game creativity, in: ICCC, 2014.
[7] G. A. Wiggins, A preliminary framework for description, analysis and comparison of
creative systems, Knowledge-Based Systems 19 (2006) 449–458.
[8] G. Ritchie, Some empirical criteria for attributing creativity to a computer program, Minds
and Machines 17 (2007) 67–99.
[9] M. A. Boden, et al., The creative mind: Myths and mechanisms, Psychology Press, 2004.
[10] P. Sarkar, A. Chakrabarti, J. Gero, Studying engineering design creativity, in: Workshop
on Studying Design Creativity, 2008.
[11] C. Shannon, A mathematical theory of communication, The Bell System Technical Journal
27 (1948) 379–423,623–656.
[12] S. McGregor, Algorithmic information theory and novelty generation, Programme
Committee and Reviewers (2007) 109.
[13] A. Vinhas, F. Assunção, J. Correia, A. Ekárt, P. Machado, Fitness and novelty in evolutionary
art, in: International Conference on Computational Intelligence in Music, Sound, Art and
Design, Springer, 2016, pp. 225–240.
[14] I. Koumarelas, A. Kroschk, C. Mosley, F. Naumann, Experience: Enhancing address
matching with geocoding and similarity measure selection, Journal of Data and Information
Quality 10 (2018) 1–16.
[15] A. Roli, A. Ligot, M. Birattari, Complexity measures: open questions and novel opportuni-
ties in the automatic design and analysis of robot swarms, Frontiers in Robotics and AI 6
(2019) 130.
[16] M. Li, X. Chen, X. Li, B. Ma, P. M. Vitányi, The similarity metric, IEEE transactions on
Information Theory 50 (2004) 3250–3264.
[17] D. Galas, M. Nykter, G. Carter, N. Price, I. Shmulevich, Biological information as set-based
complexity, IEEE Transactions on Information Theory 56 (2010) 667–677.