Advances in Swarm Intelligence 12th

International Conference ICSI 2021

Qingdao China July 17 21 2021
Proceedings Part I Lecture Notes in
Computer Science 12689 Ying Tan
(Editor)
Visit to download the full and correct content document:
https://ebookmeta.com/product/advances-in-swarm-intelligence-12th-international-co
nference-icsi-2021-qingdao-china-july-17-21-2021-proceedings-part-i-lecture-notes-in
-computer-science-12689-ying-tan-editor/
More products digital (pdf, epub, mobi) instant
download maybe you interests ...

Artificial Intelligence and Security 7th International

Conference ICAIS 2021 Dublin Ireland July 19 23 2021
Proceedings Part I Lecture Notes in Computer Science
12736 Xingming Sun (Editor)
https://ebookmeta.com/product/artificial-intelligence-and-
security-7th-international-conference-icais-2021-dublin-ireland-
july-19-23-2021-proceedings-part-i-lecture-notes-in-computer-
science-12736-xingming-sun-editor/

Geometric Science of Information 5th International

Conference GSI 2021 Paris France July 21 23 2021
Proceedings Lecture Notes in Computer Science 12829
Frank Nielsen (Editor)
https://ebookmeta.com/product/geometric-science-of-
information-5th-international-conference-gsi-2021-paris-france-
july-21-23-2021-proceedings-lecture-notes-in-computer-
science-12829-frank-nielsen-editor/

Pattern Recognition and Computer Vision 4th Chinese

Conference PRCV 2021 Beijing China October 29 November
1 2021 Proceedings Part IV Lecture Notes in Computer
Science Huimin Ma (Editor)
https://ebookmeta.com/product/pattern-recognition-and-computer-
vision-4th-chinese-conference-prcv-2021-beijing-china-
october-29-november-1-2021-proceedings-part-iv-lecture-notes-in-
computer-science-huimin-ma-editor/

Advances in Visual Computing 16th International

Symposium ISVC 2021 Virtual Event October 4 6 2021
Proceedings Part I Lecture Notes in Computer Science
George Bebis
https://ebookmeta.com/product/advances-in-visual-computing-16th-
international-symposium-isvc-2021-virtual-event-
october-4-6-2021-proceedings-part-i-lecture-notes-in-computer-
Advances in Artificial Intelligence and Security 7th
International Conference ICAIS 2021 Dublin Ireland July
19 23 2021 Proceedings Part I in Computer and
Information Science 1422 Xingming Sun (Editor)
https://ebookmeta.com/product/advances-in-artificial-
intelligence-and-security-7th-international-conference-
icais-2021-dublin-ireland-july-19-23-2021-proceedings-part-i-in-
computer-and-information-science-1422-xingming-sun-edito/

Natural Language Processing and Chinese Computing 10th

CCF International Conference NLPCC 2021 Qingdao China
October 13 17 2021 Proceedings Part I Lu Wang

https://ebookmeta.com/product/natural-language-processing-and-
chinese-computing-10th-ccf-international-conference-
nlpcc-2021-qingdao-china-october-13-17-2021-proceedings-part-i-
lu-wang/

Spatial Data and Intelligence: Second International

Conference, SpatialDI 2021, Hangzhou, China, April
22–24, 2021, Proceedings (Lecture Notes in Computer
Science, 12753) Gang Pan (Editor)
https://ebookmeta.com/product/spatial-data-and-intelligence-
second-international-conference-spatialdi-2021-hangzhou-china-
april-22-24-2021-proceedings-lecture-notes-in-computer-
science-12753-gang-pan-editor/

Web and Big Data: 5th International Joint Conference,

APWeb-WAIM 2021, Guangzhou, China, August 23–25, 2021,
Proceedings, Part I (Lecture Notes in Computer Science)
Leong Hou U (Editor)
https://ebookmeta.com/product/web-and-big-data-5th-international-
joint-conference-apweb-waim-2021-guangzhou-china-
august-23-25-2021-proceedings-part-i-lecture-notes-in-computer-
science-leong-hou-u-editor/

Reversible Computation 13th International Conference RC

2021 Virtual Event July 7 8 2021 Proceedings Lecture
Notes in Computer Science 12805 Shigeru Yamashita
(Editor)
https://ebookmeta.com/product/reversible-computation-13th-
international-conference-rc-2021-virtual-event-
july-7-8-2021-proceedings-lecture-notes-in-computer-
 Ying Tan
Yuhui Shi (Eds.)
LNCS 12689

Advances
in Swarm Intelligence
12th International Conference, ICSI 2021
Qingdao, China, July 17–21, 2021
Proceedings, Part I
Lecture Notes in Computer Science 12689

Founding Editors
Gerhard Goos
Karlsruhe Institute of Technology, Karlsruhe, Germany
Juris Hartmanis
Cornell University, Ithaca, NY, USA

Editorial Board Members

Elisa Bertino
Purdue University, West Lafayette, IN, USA
Wen Gao
Peking University, Beijing, China
Bernhard Steffen
TU Dortmund University, Dortmund, Germany
Gerhard Woeginger
RWTH Aachen, Aachen, Germany
Moti Yung
Columbia University, New York, NY, USA
More information about this subseries at http://www.springer.com/series/7407
Ying Tan Yuhui Shi (Eds.)
•

Advances
in Swarm Intelligence
12th International Conference, ICSI 2021
Qingdao, China, July 17–21, 2021
Proceedings, Part I

123
Editors
Ying Tan Yuhui Shi
Peking University Southern University of Science
Beijing, China and Technology
Shenzhen, China

ISSN 0302-9743 ISSN 1611-3349 (electronic)

Lecture Notes in Computer Science
ISBN 978-3-030-78742-4 ISBN 978-3-030-78743-1 (eBook)
https://doi.org/10.1007/978-3-030-78743-1
LNCS Sublibrary: SL1 – Theoretical Computer Science and General Issues

© Springer Nature Switzerland AG 2021

This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the
material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,
broadcasting, reproduction on microfilms or in any other physical way, and transmission or information
storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now
known or hereafter developed.
The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication
does not imply, even in the absence of a specific statement, that such names are exempt from the relevant
protective laws and regulations and therefore free for general use.
The publisher, the authors and the editors are safe to assume that the advice and information in this book are
believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors
give a warranty, expressed or implied, with respect to the material contained herein or for any errors or
omissions that may have been made. The publisher remains neutral with regard to jurisdictional claims in
published maps and institutional affiliations.

This Springer imprint is published by the registered company Springer Nature Switzerland AG
The registered company address is: Gewerbestrasse 11, 6330 Cham, Switzerland
 Preface

This book and its companion volume, comprising LNCS volumes 12689 and 12690,
constitute the proceedings of The Twelfth International International Conference on
Swarm Intelligence (ICSI 2021) held during July 17–21, 2021, in Qingdao, China, both
on-site and online.
The theme of ICSI 2021 was “Serving Life with Swarm Intelligence.” The con-
ference provided an excellent opportunity for academics and practitioners to present
and discuss the latest scientific results and methods, innovative ideas, and advantages
in theories, technologies, and applications in swarm intelligence. The technical pro-
gram covered a number of aspects of swarm intelligence and its related areas. ICSI
2021 was the twelfth international gathering for academics and researchers working on
most aspects of swarm intelligence, following successful events in Serbia (ICSI 2020,
virtually), Chiang Mai (ICSI 2019), Shanghai (ICSI 2018), Fukuoka (ICSI 2017), Bali
(ICSI 2016), Beijing (ICSI-CCI 2015), Hefei (ICSI 2014), Harbin (ICSI 2013),
Shenzhen (ICSI 2012), Chongqing (ICSI 2011), and Beijing (ICSI 2010), which
provided a high-level academic forum for participants to disseminate their new research
findings and discuss emerging areas of research. ICSI 2021 also created a stimulating
environment for participants to interact and exchange information on future challenges
and opportunities in the field of swarm intelligence research.
Due to the ongoing COVID-19 pandemic, ICSI 2021 provided opportunities for
both online and offline presentations. On the one hand, ICSI 2021 was held normally in
Qingdao, China, but on the other hand, the ICSI 2021 technical team provided the
ability for authors who were subject to restrictions on overseas travel to present their
work through an interactive online platform or video replay. The presentations by
accepted authors were made available to all registered attendees on-site and online.
The host city of ICSI 2021, Qingdao (also spelled Tsingtao), is a major
sub-provincial city in the eastern Shandong province, China. Located on the western
shore of the Yellow Sea, Qingdao is a major nodal city on the 21st Century Maritime
Silk Road arm of the Belt and Road Initiative that connects East Asia with Europe, and
has the highest GDP of any city in the province. It had jurisdiction over seven districts
and three county-level cities till 2019, and as of 2014 had a population of 9,046,200
with an urban population of 6,188,100. Lying across the Shandong Peninsula and
looking out to the Yellow Sea to its south, Qingdao borders the prefectural cities of
Yantai to the northeast, Weifang to the west, and Rizhao to the southwest.
ICSI 2021 received 177 submissions and invited submissions from about 392
authors in 32 countries and regions (Algeria, Australia, Bangladesh, Belgium, Brazil,
Bulgaria, Canada, China, Colombia, India, Italy, Japan, Jordan, Mexico, Nigeria, Peru,
Portugal, Romania, Russia, Saudi Arabia, Serbia, Slovakia, South Africa, Spain,
Sweden, Taiwan (China), Thailand, Turkey, United Arab Emirates, UK, USA, and
Vietnam) across 6 continents (Asia, Europe, North America, South America, Africa,
and Oceania). Each submission was reviewed by at least 2 reviewers, and had on
vi Preface

average 2.5 reviewers. Based on rigorous reviews by the Program Committee members
and additional reviewers, 104 high-quality papers were selected for publication in this
proceedings, an acceptance rate of 58.76%. The papers are organized into 16 cohesive
sections covering major topics of swarm intelligence research and its development and
applications.
On behalf of the Organizing Committee of ICSI 2021, we would like to express our
sincere thanks to the International Association of Swarm and Evolutionary Intelligence
(IASEI), which is the premier international scholarly society devoted to advancing the
theories, algorithms, real-world applications, and developments of swarm intelligence
and evolutionary intelligence. We would also like to thank Peking University, Southern
University of Science and Technology, and Ocean University of China for their
co-sponsorships, and the Computational Intelligence Laboratory of Peking University
and IEEE Beijing Chapter for their technical co-sponsorships, as well as our supporters
including the International Neural Network Society, World Federation on Soft Com-
puting, International Journal of Intelligence Systems, MDPI’s journals Electronics and
Mathematics, Beijing Xinghui Hi-Tech Co., and Springer Nature.
We would also like to thank the members of the Advisory Committee for their
guidance, the members of the Program Committee and additional reviewers for
reviewing the papers, and the members of the Publication Committee for checking the
accepted papers in a short period of time. We are particularly grateful to Springer for
publishing the proceedings in the prestigious series of Lecture Notes in Computer
Science. Moreover, we wish to express our heartfelt appreciation to the plenary
speakers, session chairs, and student helpers. In addition, there are still many more
colleagues, associates, friends, and supporters who helped us in immeasurable ways;
we express our sincere gratitude to them all. Last but not the least, we would like to
thank all the speakers, authors, and participants for their great contributions that made
ICSI 2021 successful and all the hard work worthwhile.

May 2021 Ying Tan

Yuhui Shi
 Organization

General Co-chairs
Ying Tan Peking University, China
Russell C. Eberhart IUPUI, USA

Program Committee Chair

Yuhui Shi Southern University of Science and Technology, China

Advisory Committee Chairs

Xingui He Peking University, China
Gary G. Yen Oklahoma State University, USA

Technical Committee Co-chairs

Haibo He University of Rhode Island, USA
Kay Chen Tan City University of Hong Kong, China
Nikola Kasabov Auckland University of Technology, New Zealand
Ponnuthurai Nagaratnam Nanyang Technological University, Singapore
Suganthan
Xiaodong Li RMIT University, Australia
Hideyuki Takagi Kyushu University, Japan
M. Middendorf University of Leipzig, Germany
Mengjie Zhang Victoria University of Wellington, New Zealand
Qirong Tang Tongji University, China
Milan Tuba Singidunum University, Serbia

Plenary Session Co-chairs

Andreas Engelbrecht University of Pretoria, South Africa
Chaoming Luo University of Mississippi, USA

Invited Session Co-chairs

Andres Iglesias University of Cantabria, Spain
Haibin Duan Beihang University, China
viii Organization

Special Sessions Chairs

Ben Niu Shenzhen University, China
Yan Pei University of Aizu, Japan

Tutorial Co-chairs
Junqi Zhang Tongji University, China
Shi Cheng Shanxi Normal University, China

Publications Co-chairs
Swagatam Das Indian Statistical Institute, India
Radu-Emil Precup Politehnica University of Timisoara, Romania

Publicity Co-chairs
Yew-Soon Ong Nanyang Technological University, Singapore
Carlos Coello CINVESTAV-IPN, Mexico
Yaochu Jin University of Surrey, UK
Rossi Kamal GERIOT, Bangladesh
Dongbin Zhao Institute of Automation, China

Finance and Registration Chairs

Andreas Janecek University of Vienna, Austria
Suicheng Gu Google, USA

Local Arrangement Chair

Gai-Ge Wang Ocean University of China, China

Conference Secretariat
Renlong Chen Peking University, China

Program Committee
Ashik Ahmed Islamic University of Technology, Bangladesh
Rafael Alcala University of Granada, Spain
Abdelmalek Amine Tahar Moulay University of Saida, Algeria
Sabri Arik Istanbul University, Turkey
Carmelo J. A. Bastos Filho University of Pernambuco, Brazil
Sandeep Bhongade G.S. Institute of Technology, India
Sujin Bureerat Khon Kaen University, Thailand
Bin Cao Tsinghua University, China
 Organization ix

Abdelghani Chahmi Universite des Sciences et Technologie d’Oran, Algeria

Junfeng Chen Hohai University, China
Walter Chen National Taipei University of Technology, Taiwan,
China
Hui Cheng Liverpool John Moores University, UK
Shi Cheng Shaanxi Normal University, China
Prithviraj Dasgupta U. S. Naval Research Laboratory, USA
Khaldoon Dhou Texas A&M University, USA
Bei Dong Shaanxi Nomal University, China
Haibin Duan Beijing University of Aeronautics and Astronautics,
China
Hongyuan Gao Harbin Engineering University, China
Shangce Gao University of Toyama, Japan
Ying Gao Guangzhou University, China
Weian Guo Tongji University, China
Changan Jiang Osaka Institute of Technology, Japan
Mingyan Jiang Shandong University, China
Liangjun Ke Xian Jiaotong University, China
Germano Lambert-Torres PS Solutions, USA
Xiujuan Lei Shaanxi Normal University, China
Bin Li University of Science and Technology of China, China
Zhetao Li Xiangtan University, China
Jing Liu Xidian University, China
Ju Liu Shandong University, China
Qunfeng Liu Dongguan University of Technology, China
Wenlian Lu Fudan University, China
Chaomin Luo Mississippi State University, USA
Wenjian Luo Harbin Institute of Technology, China
Chengying Mao Jiangxi University of Finance and Economics, China
Bernd Meyer Monash University, Australia
Efrén Mezura-Montes University of Veracruz, Mexico
Daniel Molina Cabrera University of Granada, Spain
Sreeja N. K. PSG College of Technology, India
Linqiang Pan Huazhong University of Science and Technology,
China
Quan-Ke Pan Huazhong University of Science and Technology,
China
Endre Pap Singidunum University, Serbia
Mario Pavone University of Catania, Spain
Yan Pei University of Aizu, Japan
Mukesh Prasad University of Technology Sydney, Australia
Radu-Emil Precup Politehnica University of Timisoara, Romania
Robert Reynolds Wayne State University, USA
Yuji Sato Hosei University, Japan
Carlos Segura Centro de Investigación en Matemáticas, Mexico
Kevin Seppi Brigham Young University, USA
x Organization

Zhongzhi Shi Institute of Computing Technology, China

Joao Soares GECAD, Portugal
Xiaoyan Sun China University of Mining and Technology, China
Yifei Sun Shaanxi Normal University, China
Ying Tan Peking University, China
Qirong Tang Tongji University, China
Mladen Veinović Singidunum University, Serbia
Cong Wang Northeastern University, China
Dujuan Wang Sichuan University, China
Guoyin Wang Chongqing University of Posts and
Telecommunications, China
Rui Wang National University of Defense Technology, China
Yong Wang Central South University, China
Yuping Wang Xidian University, China
Ka-Chun Wong City University of Hong Kong, China
Shunren Xia Zhejiang University, China
Ning Xiong Mälardalen University, Sweden
Benlian Xu Changsu Institute of Technology, China
Peng-Yeng Yin National Chi Nan University, Taiwan, China
Jun Yu Niigata University, Japan
Saúl Zapotecas Martínez UAM Cuajimalpa, Mexico
Jie Zhang Newcastle University, UK
Junqi Zhang Tongji University, China
Tao Zhang Tianjin University, China
Xingyi Zhang Huazhong University of Science and Technology,
China
Xinchao Zhao Beijing University of Posts and Telecommunications,
China
Yujun Zheng Zhejiang University of Technology, China
Zexuan Zhu Shenzhen University, China
Miodrag Zivkovic Singidunum University, Serbia
Xingquan Zuo Beijing University of Posts and Telecommunications,
China

Additional Reviewers

Bao, Lin Márquez Grajales, Aldo

Chen, Yang Ramos, Sérgio
Cortez, Ricardo Rivera Lopez, Rafael
Gu, Lingchen Rodríguez de la Cruz, Juan Antonio
Han, Yanyang Vargas Hakim, Gustavo Adolfo
Hu, Yao Yu, Luyue
Lezama, Fernando Zhou, Tianwei
Liu, Xiaoxi
 Contents – Part I

Swarm Intelligence and Nature-Inspired Computing

Swarm Unit Digital Control System Simulation . . . . . . . . . . . . . . . . . . . . . 3

Eugene Larkin, Aleksandr Privalov, and Tatiana Akimenko

Natural Emergence of Heterogeneous Strategies in Artificially Intelligent

Competitive Teams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
Ankur Deka and Katia Sycara

Analysis of Security Problems in Groups of Intelligent Sensors . . . . . . . . . . 26

Karen Grigoryan, Evgeniya Olefirenko, Elena Basan, Maria Lapina,
and Massimo Mecella

Optimization of a High-Lift Mechanism Motion Generation Synthesis

Using MHS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Suwin Sleesongsom and Sujin Bureerat

Liminal Tones: Swarm Aesthetics and Materiality in Sound Art . . . . . . . . . . 46

Mahsoo Salimi and Philippe Pasquier

Study on the Random Factor of Firefly Algorithm. . . . . . . . . . . . . . . . . . . . 58

Yanping Qiao, Feng Li, Cong Zhang, Xiaofeng Li, and Zhigang Zhou

Metaheuristic Optimization on Tensor-Type Solution via Swarm

Intelligence and Its Application in the Profit Optimization in Designing
Selling Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
Frederick Kin Hing Phoa, Hsin-Ping Liu,
Yun-Heh (Jessica) Chen-Burger, and Shau-Ping Lin

An Improved Dragonfly Algorithm Based on Angle Modulation

Mechanism for Solving 0–1 Knapsack Problems . . . . . . . . . . . . . . . . . . . . . 83
Lin Wang, Ronghua Shi, Wenyu Li, Xia Yuan, and Jian Dong

A Novel Physarum-Based Optimization Algorithm for Shortest Path . . . . . . . 94

Dan Wang and Zili Zhang

Traveling Salesman Problem via Swarm Intelligence . . . . . . . . . . . . . . . . . . 106

Pei-Chen Yen and Frederick Kin Hing Phoa

Swarm-Based Computing Algorithms for Optimization

Lion Swarm Optimization by Reinforcement Pattern Search . . . . . . . . . . . . . 119

Falei Ji and Mingyan Jiang
xii Contents – Part I

Fuzzy Clustering Algorithm Based on Improved Lion Swarm

Optimization Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
Haiyan Yu, Mingyan Jiang, Dongfeng Yuan, and Miaomiao Xin

Sparrow Search Algorithm for Solving Flexible Jobshop

Scheduling Problem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140
Mingliang Wu, Dongsheng Yang, Zhile Yang, and Yuanjun Guo

Performance Analysis of Evolutionary Computation Based on Tianchi

Service Scheduling Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Jun Yu, Yuhao Li, Tianwei Zhou, Churong Zhang, Guanghui Yue,
and Yunjiao Ge

An Intelligent Algorithm for AGV Scheduling in Intelligent Warehouses . . . . 163

Xue Wu, Min-Xia Zhang, and Yu-Jun Zheng

Success-History Based Position Adaptation in Gaining-Sharing Knowledge

Based Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
Shakhnaz Akhmedova and Vladimir Stanovov

Particle Swarm Optimization

Multi-guide Particle Swarm Optimisation Control Parameter Importance

in High Dimensional Spaces. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185
Timothy G. Carolus and Andries P. Engelbrecht

Research on the Latest Development of Particle Swarm Optimization

Algorithm for Satellite Constellation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
Jia-xu Zhang and Xiao-peng Yan

Polynomial Approximation Using Set-Based Particle Swarm Optimization . . . 210

Jean-Pierre van Zyl and Andries P. Engelbrecht

Optimizing Artificial Neural Network for Functions Approximation Using

Particle Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Lina Zaghloul, Rawan Zaghloul, and Mohammad Hamdan

Two Modified NichePSO Algorithms for Multimodal Optimization . . . . . . . . 232

Tyler Crane, Andries Engelbrecht, and Beatrice Ombuki-Berman

VaCSO: A Multi-objective Collaborative Competition Particle Swarm

Algorithm Based on Vector Angles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
Libao Deng, Le Song, Sibo Hou, and Gaoji Sun

The Experimental Analysis on Transfer Function of Binary Particle

Swarm Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254
Yixuan Luo, Jianhua Liu, Xingsi Xue, Renyuan Hu, and Zihang Wang
 Contents – Part I xiii

Multi-stage COVID-19 Epidemic Modeling Based on PSO and SEIR . . . . . . 265

Haiyun Qiu, Jinsong Chen, and Ben Niu

Particle Swarms Reformulated Towards a Unified

and Flexible Framework. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
Mauro Sebastián Innocente

Ant Colony Optimization

On One Bicriterion Discrete Optimization Problem and a Hybrid Ant

Colony Algorithm for Its Approximate Solution . . . . . . . . . . . . . . . . . . . . . 289
Yurii A. Mezentsev and Nikita Y. Chubko

Initializing Ant Colony Algorithms by Learning from the Difficult

Problem’s Global Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301
Xiangyang Deng, Limin Zhang, and Ziqiang Zhu

An Ant Colony Optimization Based Approach for Binary Search . . . . . . . . . 311

N. K. Sreelaja and N. K. Sreeja

A Slime Mold Fractional-Order Ant Colony Optimization Algorithm

for Travelling Salesman Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
Ziheng Rong, Xiaoling Gong, Xiangyu Wang, Wei Lv, and Jian Wang

Ant Colony Optimization for K-Independent Average Traveling

Salesman Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333
Yu Iwasaki and Koji Hasebe

Differential Evolution

Inferring Small-Scale Maximum-Entropy Genetic Regulatory Networks

by Using DE Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
Fu Yin, Jiarui Zhou, Zexuan Zhu, Xiaoliang Ma, and Weixin Xie

Variable Fragments Evolution in Differential Evolution . . . . . . . . . . . . . . . . 358

Changshou Deng, Xiaogang Dong, Yucheng Tan, and Hu Peng

The Efficiency of Interactive Differential Evolution on Creation

of ASMR Sounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
Makoto Fukumoto

Genetic Algorithm and Evolutionary Computation

Genetic Algorithm Fitness Function Formulation for Test Data Generation

with Maximum Statement Coverage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
Tatiana Avdeenko and Konstantin Serdyukov
xiv Contents – Part I

A Genetic Algorithm-Based Ensemble Convolutional Neural Networks

for Defect Recognition with Small-Scale Samples . . . . . . . . . . . . . . . . . . . . 390
Yiping Gao, Liang Gao, Xinyu Li, and Cuiyu Wang

Biased Random-Key Genetic Algorithm for Structure Learning. . . . . . . . . . . 399

Baodan Sun and Yun Zhou

Fireworks Algorithms

Performance Analysis of the Fireworks Algorithm Versions . . . . . . . . . . . . . 415

Ira Tuba, Ivana Strumberger, Eva Tuba, Nebojsa Bacanin,
and Milan Tuba

Using Population Migration and Mutation to Improve Loser-Out

Tournament-Based Fireworks Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 423
PengCheng Hong and JunQi Zhang

Region Selection with Discrete Fireworks Algorithm for Person

Re-identification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433
Xuan Li, Tao Zhang, Xin Zhao, and Shuang Li

Fireworks Harris Hawk Algorithm Based on Dynamic Competition

Mechanism for Numerical Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 441
Wenyu Li, Ronghua Shi, Heng Zou, and Jian Dong

Enhancing Fireworks Algorithm in Local Adaptation

and Global Collaboration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 451
Yifeng Li and Ying Tan

Brain Storm Optimization Algorithm

Multi-objective Brainstorming Optimization Algorithm Based on Adaptive

Mutation Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 469
Yali Wu, Yulong Wang, and Xiaoxiao Quan

Brain Storm Optimization Algorithm Based on Formal Concept Analysis. . . . 479

Fengrong Chang, Lianbo Ma, Yan Song, and Aoshuang Dong

An Improved Brain Storm Optimization Algorithm Based on Maximum

Likelihood Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
Junfeng Chen, Xingsi Xue, and Bulgan Ninjerdene

Bacterial Foraging Optimization Algorithm

Reorganized Bacterial Foraging Optimization Algorithm for Aircraft

Maintenance Technician Scheduling Problem . . . . . . . . . . . . . . . . . . . . . . . 505
Ben Niu, Bowen Xue, Tianwei Zhou, Churong Zhang, and Qinge Xiao
 Contents – Part I xv

A Bacterial Foraging Optimization Algorithm Based on Normal

Distribution for Crowdfunding Project Outcome Prediction. . . . . . . . . . . . . . 513
Yingsi Tan, Shilian Chen, and Shuang Geng

Bacterial Foraging Optimization with Leader Selection Strategy

for Bi-objective Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523
Hong Wang, Yixin Wang, Yikun Ou, and Ben Niu

DNA Computing Methods

Stability and Hopf Bifurcation Analysis of DNA Molecular Oscillator

System Based on DNA Strand Displacement . . . . . . . . . . . . . . . . . . . . . . . 537
Tao Sun, Hui Lv, and Qiang Zhang

Dynamic Behavior Analysis of DNA Subtraction Gate with Stochastic

Disturbance and Time Delay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547
Huiwen Li, Hui Lv, and Qiang Zhang

Modeling and Analysis of Nonlinear Dynamic System with Lévy Jump

Based on Cargo Sorting DNA Robot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557
Hao Fu, Hui Lv, and Qiang Zhang

Stability and Hopf Bifurcation Analysis of Complex DNA Catalytic

Reaction Network with Double Time Delays . . . . . . . . . . . . . . . . . . . . . . . 567
Wei Chen, Hui Lv, and Qiang Zhang

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583

 Contents – Part II

Multi-objective Optimization

A Multi-objective Evolutionary Algorithm Based on Second-Order

Differential Operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
Ruizhi Wan, Yinnan Chen, and Xinchao Zhao

An Improved Evolutionary Multi-objective Optimization Algorithm Based

on Multi-population and Dynamic Neighborhood . . . . . . . . . . . . . . . . . . . . 13
Shuai Zhao, Xuying Kang, and Qingjian Ni

A Multiobjective Memetic Algorithm for Multiobjective Unconstrained

Binary Quadratic Programming Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Ying Zhou, Lingjing Kong, Lijun Yan, Shaopeng Liu, and Jiaming Hong

A Hybrid Algorithm for Multi-objective Permutation Flow Shop

Scheduling Problem with Setup Times. . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
Cuiyu Wang, Shuting Wang, and Xinyu Li

Dynamic Multi-objective Optimization via Sliding Time Window

and Parallel Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Qinqin Fan, Yihao Wang, Okan K. Ersoy, Ning Li, and Zhenzhong Chu

A New Evolutionary Approach to Multiparty Multiobjective Optimization . . . 58

Zeneng She, Wenjian Luo, Yatong Chang, Xin Lin, and Ying Tan

Swarm Robotics and Multi-agent System

Immune System Algorithms to Environmental Exploration of Robot

Navigation and Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Elakiya Jayaraman, Tingjun Lei, Shahram Rahimi, Shi Cheng,
and Chaomin Luo

Primitive Shape Recognition Based on Local Point Cloud

for Object Grasp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Qirong Tang, Lou Zhong, Zheng Zhou, Wenfeng Zhu, and Zhugang Chu

Odometry During Object Transport: A Study with Swarm

of Physical Robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
Muhanad H. M. Alkilabi, Timoteo Carletti, and Elio Tuci

Active Disturbance Rejection Control of Underwater Manipulator . . . . . . . . . 102

Qirong Tang, Daopeng Jin, Yang Hong, Jinyuan Guo, and Jiang Li
xviii Contents – Part II

Distributed Position-Force Control for Cooperative Transportation with

Multiple Mobile Manipulators. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Pengjie Xu, Jun Zheng, Jingtao Zhang, Kun Zhang, Yuanzhe Cui,
and Qirong Tang

Real-Time Sea Cucumber Detection Based on YOLOv4-Tiny and Transfer

Learning Using Data Augmentation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Thao NgoGia, Yinghao Li, Daopeng Jin, Jinyuan Guo, Jiang Li,
and Qirong Tang

Toward Swarm Robots Tracking: A Constrained Gaussian Condensation

Filter Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Shihong Duan, Hang Wu, Cheng Xu, and Jiawang Wan

Adaptive Task Distribution Approach Using Threshold Behavior Tree

for Robotic Swarm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Li Ma, Weidong Bao, Xiaomin Zhu, Meng Wu, Yutong Yuan, Ji Wang,
and Hao Chen

Map Fusion Method Based on Image Stitching for Multi-robot SLAM . . . . . 146
Qirong Tang, Kun Zhang, Pengjie Xu, Jingtao Zhang, and Yuanzhe Cui

Robotic Brain Storm Optimization: A Multi-target Collaborative Searching

Paradigm for Swarm Robotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
Jian Yang, Donghui Zhao, Xinhao Xiang, and Yuhui Shi

Distributed Multi-agent Shepherding with Consensus. . . . . . . . . . . . . . . . . . 168

Benjamin Campbell, Heba El-Fiqi, Robert Hunjet, and Hussein Abbass

Non-singular Finite-Time Consensus Tracking Protocols for Second-Order

Multi-agent Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
Yao Zou, Wenfu Yang, Zixuan Wang, Keping Long, and Wei He

UAV Cooperation and Control

Multi-UAV Cooperative Path Planning via Mutant Pigeon Inspired

Optimization with Group Learning Strategy . . . . . . . . . . . . . . . . . . . . . . . . 195
Yueping Yu, Yimin Deng, and Haibin Duan

UAV Path Planning Based on Variable Neighborhood Search Genetic

Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
Guo Zhang, Rui Wang, Hongtao Lei, Tao Zhang, Wenhua Li,
and Yuanming Song

An Improved Particle Swarm Optimization with Dual Update Strategies

Collaboration Based Task Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218
Shuang Xia, Xiangyin Zhang, Xiuzhi Li, and Tian Zhang
 Contents – Part II xix

Intelligent Intrusion Detection System for a Group of UAVs . . . . . . . . . . . . 230

Elena Basan, Maria Lapina, Nikita Mudruk, and Evgeny Abramov

Machine Learning

NiaAML2: An Improved AutoML Using Nature-Inspired Algorithms . . . . . . 243

Luka Pečnik, Iztok Fister, and Iztok Fister Jr.

Proof Searching in PVS Theorem Prover Using Simulated Annealing . . . . . . 253

M. Saqib Nawaz, Meng Sun, and Philippe Fournier-Viger

Deep Reinforcement Learning for Dynamic Scheduling of Two-Stage

Assembly Flowshop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
Xin Lin and Jian Chen

A Hybrid Wind Speed Prediction Model Based on Signal Decomposition

and Deep 1DCNN. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
Yuhui Wang, Qingjian Ni, Shuai Zhao, Meng Zhang, and Chenxin Shen

A Cell Tracking Method with Deep Learning Mitosis Detection

in Microscopy Images . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Di Wu, Benlian Xu, Mingli Lu, Jian Shi, Zhen Li, Fei Guan,
and Zhicheng Yang

A Knowledge Graph Enhanced Semantic Matching Method for Plan

Recommendation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
Rupeng Liang, Shaoqiu Zheng, Kebo Deng, Zexiang Mao, Wei Ma,
and Zhengwei Zhang

Classification of Imbalanced Fetal Health Data by PSO Based Ensemble

Recursive Feature Elimination ANN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
Jun Gao, Canpeng Huang, Xijie Huang, Kaishan Huang,
and Hong Wang

Evolutionary Ontology Matching Technique with User Involvement . . . . . . . 313

Xingsi Xue, Chaofan Yang, Wenyu Liu, and Hai Zhu

Sequential Stacked AutoEncoder-Based Artificial Neural Network

and Improved Sheep Optimization for Tool Wear Prediction . . . . . . . . . . . . 321
Fei Ding, Mingyan Jiang, Dongfeng Yuan, Falei Ji, and Haiyan Yu

Application of Internet Plus: TCM Clinical Intelligent Decision Making . . . . 331

Jun Xie, Sijie Dang, Xiuyuan Xu, Jixiang Guo, Xiaozhi Zhang,
and Zhang Yi

Parallel Random Embedding with Negatively Correlated Search . . . . . . . . . . 339

Qi Yang, Peng Yang, and Ke Tang
xx Contents – Part II

Value-Based Continuous Control Without Concrete State-Action

Value Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352
Jin Zhu, Haixian Zhang, and Zhen Pan

Exploring the Landscapes and Emerging Trends of Reinforcement Learning

from 1990 to 2020: A Bibliometric Analysis . . . . . . . . . . . . . . . . . . . . . . . 365
Li Zeng, Xiaoqing Yin, Yang Li, and Zili Li

Data Mining

NiaClass: Building Rule-Based Classification Models Using

Nature-Inspired Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
Luka Pečnik, Iztok Fister, and Iztok Fister Jr.

Mining Neighbor Frames for Person Re-identification by Global

Optimal Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
Kai Han, Jinho Lee, Lang Huang, Fangcheng Liu, Seiichi Uchida,
and Chao Zhang

Artificial Fish Swarm Algorithm for Mining High Utility Itemsets . . . . . . . . 407
Wei Song, Junya Li, and Chaomin Huang

Ensemble Recognition Based on the Harmonic Information Gain Ratio

for Unsafe Behaviors in Coal Mines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 420
Jian Cheng, Botao Jiao, Yinan Guo, and Shijie Wang

Feature Selection for Image Classification Based on Bacterial

Colony Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 430
Hong Wang, Zhuo Zhou, Yixin Wang, and Xiaohui Yan

Local Binary Pattern Algorithm with Weight Threshold

for Image Classification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 440
Zexi Xu, Guangyuan Qiu, Wanying Li, Xiaofu He, and Shuang Geng

Applying Classification Algorithms to Identify Brain Activity Patterns. . . . . . 452

Marina Murtazina and Tatiana Avdeenko

An Improved El Nino Index Forecasting Method Based

on Parameters Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
Chenxin Shen, Qingjian Ni, Shuai Zhao, Meng Zhang, and Yuhui Wang

Intrusion Detection System Based on an Updated ANN Model . . . . . . . . . . . 472

Yu Xue, Bernard-marie Onzo, and Ferrante Neri

Bayesian Classifier Based on Discrete Multidimensional

Gaussian Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480
Yihuai Wang and Fei Han
 Contents – Part II xxi

An Improved Spatial-Temporal Network Based on Residual Correction

and Evolutionary Algorithm for Water Quality Prediction . . . . . . . . . . . . . . 491
Xin Yu, Wenqiang Peng, Dongfan Xue, and Qingjian Ni

Can Argumentation Help to Forecast Conditional Stock Market Crisis

with Multi-agent Sentiment Classification? . . . . . . . . . . . . . . . . . . . . . . . . . 500
Zhi-yong Hao and Peng-ge Sun

Stock Market Movement Prediction by Gated Hierarchical Encoder. . . . . . . . 511

Peibin Chen and Ying Tan

Other Applications

Spiking Adaptive Dynamic Programming with Poisson Process . . . . . . . . . . 525

Qinglai Wei, Liyuan Han, and Tielin Zhang

Designing a Mathematical Model and Control System for the Makariza

Steam Boiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
Taha Ahmadi and Sebastián Soto Gaona

Compositional Object Synthesis in Game of Life Cellular Automata Using

SAT Solver . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543
Haruki Nishimura and Koji Hasebe

Automatic Detection of Type III Solar Radio Burst . . . . . . . . . . . . . . . . . . 553

Shicai Liu, Guowu Yuan, Chengming Tan, Hao Zhou, and Ruru Cheng

The Impact of Wechat Red Packet Feature at Achieving Users Satisfaction

and Loyalty: Wechat Users in China . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
Kamal Abubker Abrahim Sleiman, Lan Juanli, Xiangyu Cai, Wang Yubo,
Lei Hongzhen, and Ru Liu

Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577

Swarm Intelligence and Nature-Inspired
Computing
 Swarm Unit Digital Control System Simulation

Eugene Larkin1(B) , Aleksandr Privalov2 , and Tatiana Akimenko1

1 Tula State University, Tula 300012, Russia
2 Tula State Lev Tolstoy Pedagogical University, Tula 300026, Russia

Abstract. Physical swarm unit, as an object under digital control is analyzed.

It is shown, that Von Neumann digital controller, as a physical device, has new
properties in comparison with analogue controllers, namely due to sequentially
interpretation of control algorithm there are time delays between quests to sen-
sors and actuators, that cause influence on a swarm unit performance as a whole.
Flowchart of digital control system is worked out and closed loops transfer func-
tion, which takes into account real properties of Von Neumann digital controller, is
obtained. The method of time lags estimation, based on notion the interpretation
of arbitrary complexity cyclic algorithm as semi-Markov process, is proposed.
Theoretical postulates are confirmed by simulation of two-loop digital control
system functioning. Results of simulation emphatically show how data skew and
feedback lag affect on swarm unit control dynamics.

Keywords: Physical swarm unit · Object under control · Von Neumann

controller · Semi-Markov process · Transfer function · Time delay · Data skew ·
Feedback lag

1 Introduction
Basic concept of modern swarm development is complication of tasks, which decide
every unit, when solving common swarm aim problem [1–3]. When physical swarm
units operate at the environment space, the problem is to minimize a time of units
mutual control, that increase demands to units digital control systems [4]. As a rule,
for control the unit onboard equipment Von Neumann computers are used. This device,
in comparison with analogue controllers, possesses with new properties, which follows
from sequential, operator-by-operator, interpretation of algorithm [5–7], embedded into
controller. So it is necessary to spend any time to calculate action, transmitted to actuator
after receiving data from sensors [8]. Time intervals emerging between input/output data
vectors (data skew), and between input data from sensors and output data to actuators
(pure lag) affect on quality characteristics of swarm unit control system as a whole [9,
10], so they should be taken into account when design the system.
There are no any difficulties in estimation of time intervals in simple case, when
cyclic control algorithm include input-output-calculation-return operators only, but when
structure of soft, involving transactions operators, is rather complicated, there is the
problem to estimate time intervals between transactions at the stage of algorithm design.
To solve the problem one should to take into account those facts, that data, forming on

© Springer Nature Switzerland AG 2021

Y. Tan and Y. Shi (Eds.): ICSI 2021, LNCS 12689, pp. 3–12, 2021.
https://doi.org/10.1007/978-3-030-78743-1_1
4 E. Larkin et al.

swarm unit sensors outputs, are random one; data may be processed by quite different
algorithm branches, possessing quite different time complexities; algorithm includes
decision operators at branching points. So to facilitate the problem solution semi-Markov
processes theory [11–14] should be accepted as basic concept for control algorithm
simulation. Methods of swarm unit digital control system simulation at the stage of its
design in order to determine unit performance are not widespread, that confirms necessity
and relevancy of investigation in the area.

2 Features of Von Neumann Computer Control

Multi, K-loop, digital control system (DCS) structure is shown on the Fig. 1. It is rather
classic one, and includes two subsystems: linear Object Under Control (OUC) and Dig-
ital Controller (DC). OUC consists of K units, every of which is described with transfer
function vector Wk (s) = [Wk1 (s), ..., Wkl (s), ..., WkK (s)] and feedback scalar trans-
fer function W0, k (s), 1 ≤ k ≤ K. Vectors Wk (s), and scalars W0, k (s), describe the
dynamics of OUC k-th unit itself and feedback sensor, respectively. DC is real time
Von Neumann type computer, which interprets control program, and in cycle generates
quests both to actuators, and to sensors for organizing the managing procedure.

U1(s) X1(s)
F1(s) W1(s)

X0,1(z)
W0,1(s)
...
...
Uk(s)
Xk(s)
Wk(s)
Fk(s) Wc(s)

X0,k(z)
W0,k(s)

... ...
XK(s)
UK(s) WK(s)
FK(s)
X0,K(z)
W0,K(s)
DC OUC

Fig. 1. Flowchart of swarm unit digital control system

System operates as follows. The control aim vector

F(s) = [F1 (s), ..., Fk (s), ..., FK (s)] is generated element-by-element by controller,
or inputted element-by-element into DC from outside. On outputs of controller action
 Swarm Unit Digital Control System Simulation 5

vector U(s) = [U1 (s), ..., Uk (s), ..., UK (s)] is generated by software, and is physi-
cally transformed into the swarm unit state X(s) = [X1 (s), ..., Xk (s), ..., XK (s)] as
follows:
⎡ ⎤
W1 (s)
⎢ ... ⎥
⎢ ⎥
⎢ ⎥
X(s) = U(s) · W(s) = U(s) · ⎢ Wk (s) ⎥, (1)
⎢ ⎥
⎣ ... ⎦
WK (s)

where s is the Laplace operator [15].

 OUC state is measured by K sensors, and vector signal X0 (s) =
X0, 1 (s), ..., X0, k (s), ..., X0, K (s) is inputted into DC back, sequentially, element-
by-element. Due to time intervals between transactions are essential values for DC
description, below is considered, that they are counted from moment of input of the first.
All other data are input/output respectively element F1 (s) ∈ F(s) with lags, nominated
as follows:

Fk (s) are inputted respectively F1 (s) with lags τf , k , 2 ≤ k ≤ K;

X0, k (s) are inputted respectively F1 (s) with lags τ0, k , 1 ≤ k ≤ K;
Uk (s) are outputted respectively F1 (s) with lags τu, k , 1 ≤ k ≤ K.

In accordance with the theorem about shifting in the time domain [15, 16]

L[ϕ(t − τ )] = exp(−τ s)(s), τ > 0, (2)

where τ is the shifting value; t is the time; ϕ(t) is a function; L[...] - direct Laplace
transform: (s) is the Laplace transform of ϕ(t).
From (2) it follows, that

Fsh (s) = F(s) · Qf (s); (3)

Xsh (s) = X0 (s) · Q0 (s); (4)

Ush (s) = U(s) · Qu (s), (5)

where Fsh (s), Xsh (s), Ush (s) are vectors F(s), X0 (s), U(s), elements of which are delayed
on time; Qf (s) = Qf , kl (s) , Q0 (s) = Q0, kl (s) , Qv (s) = Qu, kl (s) are diagonal lag
matrices, in which
⎧
⎨ 0, when k = l;
Qf , kl (s) = 1, when k = l = 1; (6)
⎩  
exp −τf , k s , when 2 ≤ k = l ≤ K;

0, when
 k = l;
Q0, kl (s) = (7)
exp −τ0, k s , when k = l;
6 E. Larkin et al.


0, when
 k = l;
Qu, kl (s) = (8)
exp −τu, k s , when k = l.

Data, processed in DC, are discrete one, so in strict sense, ordinary transfer function
apparatus is not fit for description of U(s) vector elements calculation. But, when sam-
pling period is approached to zero, then data processing in frequency domain may be
described as ordinary transfer function matrix Wc (s). So, in the case, when, processing
feedback signal, DC realizes a linear control law, on its outputs U(s) the following vector
signal is generated [5, 6]:

U(s) = F(s) · Qf (s) − X(s) · W0 (s) · Q0 (s) · Wc (s) · Qu (s), (9)

where Wc (s) = Wc, kl (s) is the K × K matrix of linear transfer functions, which are
embedded into DC as a software; W0 (s) = W0, kl (s) is the K × K diagonal matrix,
whose elements are as follows:

0, when k = l;
W0, kl (s) = (10)
W0, k (s), when k = l.

Simultaneous solution of (9) and (11) relatively to X(s) gives the following
expression

X(s) = [E − W0 (s) · Q0 (s) · Wc (s) · Qu (s)]−1

(11)
× F(s) · Wc (s) · Qf (s) · W(s) · Qu (s),

where E is the K × K unit diagonal matrix;

Matrices Qf (s) = Qf , kl (s) , Q0 (s) = Q0, kl (s) , Qv (s) = Qu, kl (s) , character-
izing lags, are situated both in the numerator, and in denominator of (12). Matrices sit-
uated at numerator, defines so called data skew and common lag of external commands
execution. Matrices situated at denominator, defines common feedback lag, therefore
changes qualitatively characteristics of transition process.

3 Semi-Markov Model of DC Operation

For estimation of time intervals the model of Von Neumann computer operation in time
domain should be worked out. For simplicity it may be represented as including trans-
action operators only. Control process in such model is reduced to elements of vectors
F(s), X0 (s) reading from interface and elements of vector U(s) writing to interface.
The algorithm, generated quests, is the cyclic one, but in it absent a looping effect. The
algorithm may generate transactions in an arbitrary sequence, with one exception; the
same transaction can not be generated twice at a time. Also, due to the fact, that for
control action U(s) calculation all element of vectors F(s) and X0 (s) should be used,
the strong connectivity condition should be imposed [17, 18] on the graph, which, rep-
resents the structure of control algorithm. In common case such properties has the full
oriented graph without loops, shown on the Fig. 2 a. In simplest case vectors F(s) and
 Swarm Unit Digital Control System Simulation 7

X0 (s) elements are quested in turn, after that control action is calculated, and after that
elements of U(s) are quested in turn (Fig. 2 b).
With taking into account randomness of time interval between transactions and
stochastic transactions sequence for external observer, the adequate approach to algo-
rithm simulation is semi-Markov process [11–14], which states are abstract analogues
of algorithm operators. Semi-Markov process is represented by the semi-Markov matrix
 
h(t) = [hkl (t)] = gkl (t) ⊗ pkl (t) , (12)

where pkl (t) is probability of the direct switching from the k-th state to the l-th state;
gkl (t) is the time density of residence the process (17) in the k-th state before switching
into the l-th state; ⊗ is the direct multiplication sign; t is the physical time.

1 k 1 k

3K l 3K l

a c

1 ... k ... l ... 3K

Fig. 2. Common structure of semi-Markov process (a), simplest case (b) and the model for time
interval estimation (c)

Semi-Markov process (13) is ergodic one and does not include both absorbing, and
partially absorbing states. Due to semi-Markov process ergodicity on densities gk, l (t)
and probabilities pk, l (t) following restrictions are imposed:

0 < Tklmin ≤ arg[gkl (t)] ≤ Tklmin < ∞, 1 ≤ k, l ≤ 3K; (13)


3K
pkl = 1; (14)
l=1

where 3K is common quantity of transaction operators; Tklmin and Tklmax are upper and
lower bounds of density gkl (t) domain.
When estimation of time intervals between transactions it is no matter how semi-
Markov process (13) gets l-th state from the first one. Determining in the case is that
8 E. Larkin et al.

switch is the first, but not second, third, etc. For time interval estimation initial semi-
Markov process should be transformed into the process with the structure, shown on the
Fig. 2 c, in which first state is the starting one, and l-th state is the absorbing one. For
getting such structure:

First column and l-th row of h(t) are reset to zeros;

Probabilities pki (t) in all rows excluding the l-th, and in all columns, excluding the first,
are recalculated as follows:
 pki
pki = , 1 ≤ k, i ≤ 3K, k = l, i = 1. (15)
1 − pk1

In such a way

h(t) → h (t) = gkl (t) · pkl

. (16)

After recalculation probabilities according (15), partially absorbing states are anni-
hilated, and events of getting the l-th state from the first state begin to make up a full
group of incompatible events. In such a way, time density of wandering from the first
state to the l-th state may be estimated as follows [19]
⎡ ⎤
∞

−1 ⎣
  

L h (t) ⎦ · Ilc ,
j
l (t) = I1 · L
r
g1, (17)
j=1

where L−1 [...] is the inverse Laplace transform; I1r is the row-vector, first element of
which is equal to one, and other elements are equal to zeros; Ilc is the column-vector,
l-th element of which is equal to one, and other elements are equal to zeros.
For time density (19) the expectation and the dispersion may be calculated, as usual
[20]:
∞
T1l = 
t · g1l (t)dt; (18)
0
∞

 2 
D1l = t − T1l · g1l (t)dt (19)
0

In simplest case density, expectation and dispersion of reaching time the l-th state
from the first, are as follows:
 l−1 
 

g1l (t) = L−1 L gk, k+1 (t) , (20)
k=1


l
T1l (t) = Tk, k+1 ; (21)
k=1
 Swarm Unit Digital Control System Simulation 9


l

D1l (t) = Dk, k+1 ; (22)
k=1

where gk, k+1 (t), Tk, k+1 , Dk, k+1 (t) are density, expectation and dispersion of time of
residence the process, shown on the Fig. 2 c, in the k-th state before switching into the
(k + 1)-th state.
Expectations T1l (t) = τ1l give middle estimations of time delays. Also time intervals
may be estimated with using “three sigma rule” [21], as follows:

τ1l = T1l + 3 D1l. (23)

Estimations (17)–(23) define lags of input/output vectors F(s), X0 (s), U(s) elements
with respect to input the element F1 (s). All other delays may be obtained from these
parameters. For example, delay between input of k-th element, 1 ≤ l ≤ 2K and output
of l-th element 2K + 1 ≤ m ≤ 3K may be defined as

τkl = τ1l − τ1k . (24)

When obtaining swarm unit control system closed loop transfer function according
(11) estimations (18), (21), or (23) may be used.

4 Example of Control System Analysis

As an example, swarm unit two-loop digital control system is considered (Fig. 3).
Structure of algorithm, realized in DC, is shown on the Fig. 2 b.

-
W11(s)
F1(s) U1(s) X1(s)

W21(s)
DC OUC
W12(s)
X2(s)
F2(s) U2(s)
W22(s)

Fig. 3. Swarm unit two-loop digital control system

10 E. Larkin et al.

Transfer functions, which define OUC dynamics are as follows:

5 2
W11 (s) = W22 (s) = ; W12 (s) = W21 (s) = . (25)
0, 2s + 1 0, 2s + 1
In the system proportional feedback is realized. Sensors, which measure state vector
[X1 (s), X1 (s)] of OUC, are characterized by transfer functions W0, 1 (s) = W0, 2 (s) = 1.
Inputs F1 (s) and F2 (s) are Laplace transform of Heaviside functions L−1 [F1 (s)] =
1·η(t), L−1 [F2 (s)] = 0.5·η(t). Values of Heaviside functions are established differently
to divide plots on ordinate axis. Transition processes are shown on the Fig. 4. Plots on
all charts, shown on the Fig. 4 have the same nominations, namely x1 (t) = L−1 [X1 (s)]
x2 (t) = L−1 [X2 (s)], when data skew of vector [F1 (s), F2 (s)] is absent; x1, τ (t), x2, τ (t)
denote signals x1 (t), x2 (t), when under experimental conditions signal x2 (t) lag behind
signal x1 (t) at 0,5 s.

Fig. 4. Plots of transtion processes

Figure 4 a shows transition processes, when controller in the system is an analogue

one. As one can see at the plots, the system is absolutely stable and have good perfor-
mance, both when a data skew in the signals F1 (s), F2 (s) is absent, and when the skew
take place. Figure 4 b, c, d show transition processes, when data lags at interfaces are:

Figure 4 b - τU , 1 = 0, 02 s, τU , 2 = 0, 025 s, τ0, 1 = 0, 01 s, τ0, 2 = 0, 015 s;

Figure 4 c - τU , 1 = 0, 025 s, τU , 2 = 0, 03 s, τ0, 1 = 0, 015 s, τ0, 2 = 0, 02 s;
Figure 4 d - τU , 1 = 0, 03 s, τU , 2 = 0, 035 s, τ0, 1 = 0, 02 s, τ0, 2 = 0, 025 s.
 Swarm Unit Digital Control System Simulation 11

At all named plots processes start with delays, which are defined by output lags
of signals U1 (s), U2 (s). Figure 4 b demonstrates in general a stable system, but with
increased overshooting and time of reaching the mode. Figure 4 c demonstrate the
performance of system, close to stability border, and Fig. 4 c shows fully unstable
system.

5 Conclusion

As a result, the mathematical model of physical swarm unit digital control system,
which takes into account real characteristics of Von Neumann type controllers, is worked
out. Method of estimation of time intervals between transactions, generated by digital
controller algorithm of arbitrary complexity, to unit actuators and sensors, is proposed. It
is shown, that time delays between input/output elements of the same vector (data skew),
and between input of data from sensors and output data to actuators (feedback lag) causes
deterioration of swarm unit performance characteristics, such as overshooting and time
of reaching the mode. The results of investigation may be recommended for utilization
in ingineering practice of swam unit soft design.
Further investigations in the domain may be directed to working out methods of
practical swarm control algorithms synthesis, optimal to complexity-quality ratio.
The research was supported by the Foundation for Basic Research under the project
19-47-710004 r_a.

References
1. Bouallègue, S., Haggège, J., Ayadi, M., Benrejeb, M.: PID-type fuzzy logic controller tuning
based on particle swarm optimization. Eng. Appl. Artif. Intell. 25(3), 484–493 (2012). https://
doi.org/10.1016/j.engappai.2011.09.018
2. Reyes-Sierra, M., Coello Coello, C.A.: Multi-objective particle swarm optimizers: a survey
of the state-of-the-art. Int. J. Comput. Intell. Res. 2(3), 287–308 (2006). https://doi.org/10.
5019/j.ijcir.2006.68
3. Babishin, V., Taghipour, S.: Optimal maintenance policy for multicomponent systems with
periodic and opportunistic inspections and preventive replacements. Appl. Math. Model.
40(23), 10480–10505 (2016). https://doi.org/10.1016/j.apm.2016.07.019
4. Larkin, E., Antonov, M.: On assessing the temporal characteristics of reaching the milestone
by a swarm. In: Tan, Y., Shi, Y., Tuba, M. (eds.) ICSI 2020. LNCS, vol. 12145, pp. 46–55.
Springer, Cham (2020). https://doi.org/10.1007/978-3-030-53956-6_5
5. Landau, I.D., Zito, G.: Digital Control Systems, Design, Identification and Implementation,
p. 484. Springer, Heidelberg (2006)
6. Aström, J., Wittenmark, B.: Computer Controlled Systems: Theory and Design, p. 557.
Tsinghua University Press. Prentice Hall (2002)
7. Fadali, M.S., Visioli, A.: Digital Control Engineering: Analysis and Design, pp. 239–272.
Elsevier Inc. (2013)
8. Larkin, E.V., Ivutin, A.N.: Estimation of latency in embedded real-time systems. In: 3rd
Meditteranean Conference on Embedded Computing (MECO-2014), Budva, Montenegro,
pp. 236–239 (2014)
12 E. Larkin et al.

9. Auslander, D.M., Ridgely, J.R., Jones, J.C.: Real-time software for implementation of feed-
back control. In: Levine, W.S. (ed.) The Control Handbook. Control System Fundamentals,
pp. 16-1–16-32. CRC Press. Taylor and Francis Group (2017)
10. Karnopp, D.C., Margolis, D.L., Rosenberg, R.C.: System Dynamics: Modeling, Simulation
and Control of Mechatronic Systems, p. 636. Hoboken, Willey (2012)
11. Bielecki, T., Jakubowski, J., Niew˛egłowski, M.: Conditional Markov chains: properties, con-
struction and structured dependence. Stochast. Process. Appl. 127(4), 1125–1170 (2017).
https://doi.org/10.1016/j.spa.2016.07.010
12. Ching, W.K., Huang, X., Ng, M.K., Siu, T.K.: Markov Chains: Models, Algorithms and
Applications. International Series in Operations Research & Management Science, vol. 189,
p. 241. Springer, New York (2013)
13. Howard, R.A.: Dynamic Probabilistic Systems, vol. 1: Markov Models. vol. II: Semi-Markov
and Decision Processes. Courier Corporation (2012)
14. Janssen, J., Manca, R.: Applied Semi-Markov Processes, p. 310. Springer, Heidelberg (2006)
15. Schiff, J.L.: The Laplace Transform: Theory and Applications, p. 233. Springer, New York
(1991)
16. Li, J., Farquharson, C.G., Hu, X.: Three effective inverse Laplace transform algorithms for
computing time -domain electromagnetic responses. Geophysics 81(2), E75–E90 (2015)
17. Arnold, K.A.: Timing analysis in embedded systems. In: Ganssler, J., Arnold, K., et al. (eds.)
Embedded Hardware, pp. 239–272. Elsevier Inc. (2008)
18. Balsamo, S., Harrison, P., Marin, A.: Methodological construction of product-form stochastic
Petri nets for performance evaluation. J. Syst. Softw. 85(7), 1520–1539 (2012). https://doi.
org/10.1016/j.jss.2011.11.1042
19. Larkin, E., Akimenko, T., Privalov, A.: Synchronized swarm operation. In: Tan, Y., Shi, Y.,
Tuba, M. (eds.) Advances in Swarm Intelligence, ICSI 2020, pp. 15–24. Springer, Cham
(2020). https://doi.org/10.1007/978-3-030-53956-6_2
20. Kobayashi, H., Marl, B.L., Turin, W.: Probability, Random Processes and Statistical Analysis,
p. 812. Cambridge University Press (2012)
21. Pukelsheim, F.: The three sigma rule. Am. Stat. 48(2), 88–91 (1994)
 Natural Emergence of Heterogeneous
Strategies in Artificially Intelligent
Competitive Teams

Ankur Deka(B) and Katia Sycara

Robotics Institute, Carnegie Mellon University, Pittsburgh, PA 15213, USA

{adeka,katia}@cs.cmu.edu

Abstract. Multi agent strategies in mixed cooperative-competitive

environments can be hard to craft by hand because each agent needs
to coordinate with its teammates while competing with its opponents.
Learning based algorithms are appealing but they require a compet-
itive opponent to train against, which is often not available. Many
scenarios require heterogeneous agent behavior for the team’s success
and this increases the complexity of the learning algorithm. In this
work, we develop a mixed cooperative-competitive multi agent envi-
ronment called FortAttack in which two teams compete against each
other for success. We show that modeling agents with Graph Neu-
ral Networks (GNNs) and training them with Reinforcement Learning
(RL) from scratch, leads to the co-evolution of increasingly complex
strategies for each team. Through competition in Multi-Agent Rein-
forcement Learning (MARL), we observe a natural emergence of hetero-
geneous behavior among homogeneous agents when such behavior can
lead to the team’s success. Such heterogeneous behavior from homo-
geneous agents is appealing because any agent can replace the role
of another agent at test time. Finally, we propose ensemble training,
in which we utilize the evolved opponent strategies to train a single
policy for friendly agents. We were able to train a large number of
agents on a commodity laptop, which shows the scalability and effi-
ciency of our approach. The code and a video presentation are available
online (Code: https://github.com/Ankur-Deka/Emergent-Multiagent-
Strategies, Video: https://youtu.be/ltHgKYc0F-E).

Keywords: Multi-Agent Reinforcement Learning (MARL) · Graph

Neural Networks (GNNs) · Co-evolution

1 Introduction
Multi agent systems can play an important role in scenarios such as disaster
relief, defense against enemies and games. There have been studies on various
Supported by organization ONR N00014-19-C-1070, AFOSR/AFRL award FA9550-
18-1-0251, Darpa DARPA Cooperative Agreement No.: HR00111820051 and AFOSR
FA9550-15-1-0442.
c Springer Nature Switzerland AG 2021
Y. Tan and Y. Shi (Eds.): ICSI 2021, LNCS 12689, pp. 13–25, 2021.
https://doi.org/10.1007/978-3-030-78743-1_2
14 A. Deka and K. Sycara

Fig. 1. The FortAttack environment in which guards (green) need to protect the fort
(cyan semicircle at the top) from the attackers (red). The attackers win when any one
of them reaches the fort. Each agent can shoot a laser which can kill an opponent.

aspects of it including task assignment [16], resilience to failure [12], scalability [1]
and opponent modeling [23]. Multi agent systems become increasingly complex
in mixed cooperative-competitive scenarios where an agent has to cooperate with
other agents of the same team to jointly compete against the opposing team. It
becomes difficult to model behavior of an agent or a team by hand and learning
based methods are of particular appeal.
Our goal is to develop a learning based algorithm for decentralized control of
multi agent systems in mixed cooperative-competitive scenarios with the abil-
ity to handle a variable number of agents, as some robots may get damaged in
a real world scenario or some agents may get killed in a game. To be able to
handle a variable number of agents and to scale to many agents, we propose to
use a Graph Neural Networks (GNNs) based architecture to model inter-agent
interactions, similar to [1] and [3]. This approach relies on shared parameters
amongst all agents in a team which renders all of them homogeneous. We aim
to study if heterogeneous behavior can emerge out of such homogeneous agents.

Our contributions in this work are:

– We have developed a mixed cooperative-competitive multi agent environment
called FortAttack with simple rules yet room for complex multi agent behav-
ior.
– We show that using GNNs with a standard off the shelf reinforcement learning
algorithm can effectively model inter agent interactions in a competitive multi
agent setting.
– To train strong agents we need competitive opponents. Using an approach
inspired by self play, we are able to create an auto curriculum that generates
strong agents from scratch without using any expert knowledge. Strategies
naturally evolved as a winning strategy from one team created pressure for the
other team to be more competitive. We were able to achieve this by training
on a commodity laptop.
– We show that highly competitive heterogeneous behavior can naturally
emerge amongst homogeneous agents with symmetric reward structure
 Natural Emergence of Multi-agent AI Strategies 15

(within the same team) when such behavior can lead to the team’s success.
Such behavior implicitly includes heterogeneous task allocation and complex
coordination within a team, none of which had to be explicitly crafted but
can be extremely beneficial for multi agent systems.

2 Related Work
2.1 Multi-agent Reinforcement Learning
The recent successes of reinforcement learning in games, [11,17] and robotics, [6,
15] have encouraged researchers to extend reinforcement learning to multi agent
settings.
There are three broad categories of approaches used, centralized, decentral-
ized and a mix of the two. Centralized approaches have a single reinforcement
learning agent for the entire team, which has global state information and selects
joint actions for the team. However, the joint state and action spaces grows expo-
nentially with the number of agents rendering centralized approaches difficult to
scale [5].
Independent Q-learning, [19,20] is a decentralized approach where each agent
learns separately with Q-learning, [22] and treats all other agents as parts of the
environment. Inter agent interactions are not explicitly modeled and performance
is generally sub-par.
Centralized learning with decentralized execution has gained attention
because it is reasonable to remove communication restrictions at training time.
Some approaches use a decentralized actor with a centralized critic, which is
accessible only at training time. MADDPG, [10] learns a centralized critic for
each agent and trains policies using DDPG, [9]. QMIX, [13] proposes a mono-
tonic decomposition of action value function. However, the use of centralized
critic requires that the number of agents be fixed in the environment.
GridNet, [7] addresses the issue of multiple and variable number of agents
without exponentially growing the policy representation by representing a pol-
icy with an encoder-decoder architecture with convolution layers. However, the
centralized execution realm renders it infeasible in many scenarios.
Graphs can naturally model multi agent systems with each node representing
an agent. [18] modeled inter agent interactions in multi agent teams using GNNs
which can be learnt through back propagation. [8] proposed to use attention
and [1] proposed to use an entity graph for augmenting environment information.
However, these settings don’t involve two opposing multi agent teams that both
evolve by learning.
[3] explored multi agent reinforcement learning for the game of hide and
seek. They find that increasingly complex behavior emerge out of simple rules of
the game over many episodes of interactions. However, they relied on extremely
heavy computations spanning over many millions of episodes of environment
exploration.
We draw inspiration from [1] and [3]. For each team we propose to have two
components within the graph, one to model the observations of the opponents
16 A. Deka and K. Sycara

and one to model the interactions with fellow team mates. Our work falls in the
paradigm of centralized training with decentralized execution. We were able to
train our agents in the FortAttack environment using the proposed approach on
a commodity laptop. We believe that the reasonable computational requirement
would encourage further research in the field of mixed cooperative-competitive
MARL.

2.2 Multi-agent Environments

Although there are many existing multi-agent environments, they suffer from
the following deficiencies:
– Multi-Agent Particle Environment (MAPE) [10] doesn’t consider competitive
scenarios (2 competiting teams).
– StarCraft II Learning Environment (SC2LE) [21] assumes a centralized con-
troller for all agents in a team which is impractical for real world scenarios.
– Starcraft Multi-Agent Challenge (SMAC) [14] doesn’t incorporate learning
based opponents.
– RoboSumo [2] Doesn’t scale to many agents (only contains 1 vs 1 scenarios).
Moreoever, SC2LE [21], SMAC [14] and SoboSumo [2] are computationally heavy
environments.
To overcome these deficiencies, we design a new light-weight (can run on
commodity laptop) mixed cooperative-competitive environment called FortAt-
tack (Fig. 1) which can handle (1) Large number of agents, (2) Decentralized
controllers, (3) Learning based opponents, (4) Variable number of agents within
a single episode and (5) Complex multi-agent strategies as is evident from our
results (Sect. 5.1).

3 Method
The agents in a multi-agent team can be treated as nodes of a graph to lever-
age the power of Graph Neural Networks (GNNs). GNNs form a deep-learning
architecture where the computations at the nodes and edges of the graph are
performed by neural networks (parameterized non-linear functions), [1]. Due to
the presence of graph structure and multiple neural networks, they are called
GNNs.
We describe our use of GNNs from the perspective of one team and use Xi
to denote the state of ith friendly agent in the team, which in our case is its
position, orientation and velocity. We use XOppj to denote the state of the j th
opponent in the opposing team. Let S = {1, 2, . . . , N1 } denote the set of friendly
agents and SOpp = {N1 + 1, N1 + 2, . . . , N1 + N2 } denote the set of opponents.
Note that a symmetric view can be presented from the perspective of the other
team.
In the following, we describe how agent 1 processes the observations of its
opponents and how it interacts with its teammates. Figure 2 shows this pictori-
ally for a 3 agents vs 3 agents scenario. All the other agents have a symmetric
representation of interactions.
 Natural Emergence of Multi-agent AI Strategies 17

Fig. 2. Modeling of inter agent interactions with Graph Neural Networks (GNNs) from
the perspective of agent 1, in a 3 friendly agents vs 3 opponents scenario. Left: agent
1’s embedding, H10 is formed by taking into consideration the states of all opponents
through an attention layer. Right: agent 1’s embedding gets updated, (H1k → H1k+1 )
by taking into consideration its team mates through an attention layer.

3.1 Modeling Observation of Opponents

Friendly agent 1 takes its state, X1 and passes it through a non-linear function,
fθa to generate an embedding, h1 . Similarly, it forms an embedding, hOppj from
each of its opponents with the function fθb .

h1 = fθa (X1 ) (1)

hOppj = fθb (XOppj ) ∀j ∈ SOpp (2)

Note that the opponents don’t share their information with the friendly agent
1. Friendly agent 1 merely makes its own observation of the opponents. It then
computes a dot product attention, ψ1j which describes how much attention it
pays to each of its opponents. The dimension of h1 and hOppj are d1 each. This
attention allows agent 1 to compute a joint embedding, e1 of all of its opponents.

1
ψ̂1j = < h1 , hOppj > ∀j ∈ SOpp (3)
d1
exp(ψ̂1j )
ψ1j =  (4)
m∈SOpp exp(ψ̂1m )

e1 = ψ1j hOppj (5)
j∈SOpp

In Eq. 3, <, > denotes vector dot product. Note that j∈SOpp ψ1j = 1 which
ensures that the net attention paid by agent 1 to its opponents is fixed. Finally,
e1 is concatenated with h1 to form an agent embedding, H10 :

H10 = concatenate(h1 , e1 ) (6)

18 A. Deka and K. Sycara

3.2 Modeling Interactions with Teammates

Agent 1 forms an embedding for each of its team mates with the non-linear
function, fθa .
Hi0 = fθa (Xi ) ∀i ∈ S, i = 1 (7)
Dimension of Hik , ∀i ∈ S is d2 . Agent 1 computes a dot product attention, φ1i
with all of its team mates and updates it’s embedding with a non-linear function,
fθc .
1
φ̂1i = < H1k , Hik > ∀i ∈ S, i = 1 (8)
d2
exp(φ̂1i )
φ1i =  (9)
m∈S,m=1 exp(φ̂1m )

Ĥ1k+1 = φ1i Hik (10)
i∈S,i=1

H1k+1 = fθc (Ĥ1k+1 ) (11)

Equations, 8 to 11 can be run over multiple iterations for k = {0, 1, . . . , K} to
allow information propagation to other agents if agents can perceive only its
local neighborhood similar to [1].

3.3 Policy
The final embedding of friendly agent 1, H1K is passed through a policy head. In
our experiments, we use a stochastic policy in discrete action space and hence
the policy head has a sigmoid activation which outputs a categorical distribution
specifying the probability of each action, αm .
π(αm |O1 ) = π  (αm |H1K ) = sigmoid(fθd (H1K )) (12)
where, O1 = {Xi : i ∈ S} ∪ {XOppj : j ∈ SOpp }
Here, O1 is the observation of agent 1, which consists of its own state and the
states of all other agents that it observes. This corresponds to a fully connected
graph. We do this for simplicity. In practice, we could limit the observation space
of an agent within a fixed neighborhood around the agent similar to [1] and [3].

3.4 Scalability and Real World Applicability

Due to the use of GNNs, the learn-able parameters for a team are the shared
parameters, θa , θb , θc and θd of the functions, fθa , fθb , fθc and fθd , respectively
which we model with fully connected neural networks. Note that the number
of learn-able parameters is independent of the number of agents and hence can
scale to a large number of agents. This also allows us to handle a varying number
of agents as agents might get killed during an episode and makes our approach
applicable to real world scenarios where a robot may get damaged during a
mission.
 Natural Emergence of Multi-agent AI Strategies 19

Table 1. Reward structure

Sl. No. Event Reward

1 Guard i leaves the fort Guard i gets -1 reward.
2 Guard i returns to the fort Guard i gets +1 reward.
3 Attacker j moves closer to the Attacker j gets small +ve
fort reward = 2[Dj (t − 1) − Dj (t)].
Where, Dj (t) = distance
between attacker and fort at
time t.
4 Attacker j moves away from the Attacker j gets small -ve reward
fort = −2[Dj (t − 1) − Dj (t)].
5 Guard i shoots attacker j with Guard i gets +3 reward and
laser attacker j gets -3 reward.
6 Attacker j shoots guard i with Guard i gets -3 reward and
laser attacker j gets +3 reward.
7 Agent i shoots laser but doesn’t Agent i gets low -ve reward
hit any opponent (-0.1 if guard, -1 if attacker).
8 All attackers are killed All alive guards get high +ve
reward (+10). Attacker(s) that
just got killed gets high -ve
(-10) reward.
9 Attacker j reaches the fort All alive guards high -ve reward.
Attacker j gets high +ve reward

3.5 Training

Our approach follows the paradigm of centralized training with decentralized

execution. During training, a single set of parameters are shared amongst team-
mates. We train our multi agent teams with Proximal Policy Optimization
(PPO), [15]. At every training step, a fixed number of interactions are collected
from the environment using the current policy for each agent and then each team
is trained separately using PPO.
The shared parameters naturally share experiences amongst teammates and
allow for training with fewer number of episodes. At test time, each agent main-
tains a copy of the parameters and can operate in decentralized fashion. We
trained our agents on a commodity laptop with i7 processor and GTX 1060
graphics card. Training took about 1–2 days without parallelizing the environ-
ment.

4 Environment

We design a mixed cooperative-competitive environment called Fortattack with

OpenAI Gym, [4] like interface. Figure 1 shows a rendering of our environment.
20 A. Deka and K. Sycara

Fig. 3. Average reward per agent per episode for the teams of attackers and guards as
training progresses. The reward plots have distinct extrema and corresponding snap-
shots of the environment are shown. The x-axis shows the number of steps of environ-
ment interaction. The reward is plotted after Gaussian smoothing.

The environment consists of a team of guards, shown in green and a team of

attackers, shown in red, that compete against each other. The attackers need to
reach the fort which is shown as a cyan semi-circle at the top. Each agent can
shoot a laser beam which can kill an opponent if it is within the beam window.
At the beginning of an episode, the guards are located randomly near the
fort and the attackers are spawned at random locations near the bottom of the
environment. The guards win if they manage to kill all attackers or manage to
keep them away for a fixed time interval which is the episode length. The guards
lose if even one attacker manages to reach the fort. The environment is built off
of Multi-Agent Particle Environment [10].

4.1 Observation Space

Each agent can observe all the other agents in the environment. Hence, the
observation space consists of states (positions, orientations and velocities) of
team mates and opponents. We assume full observability as the environment
 Natural Emergence of Multi-agent AI Strategies 21

(a) Random exploration

(b) Laser flashing strategy of guards

(c) Sneaking strategy of attackers

(d) Spreading and flashing strategy of guards

(e) Deception strategy of attackers

(f ) Smartly spreading strategy of guards

Fig. 4. Sample sequences for different strategies that evolved during training. Each
row represents one sequence and time moves from left to right.
22 A. Deka and K. Sycara

Fig. 5. Average reward per agent per episode for guards as ensemble training pro-
gresses. The reward is shown after Gaussian smoothing.

is small in size. This can possibly be extended to observability in the local

neighborhood such as in [1] and [3].

4.2 Action Space

At each time step, an agent can choose one of 7 actions, accelerate in ±x direc-
tion, accelerate in ±y direction, rotate clockwise/anti-clockwise by a fixed angle
or do nothing.

4.3 Reward Structure

Each agent gets a reward which has components of its individual and the team’s
performance as described in Table 1. The last two rows show the major reward
signals corresponding to winning and losing. The negative reward for wasting a
laser shot is higher in magnitude for attackers than for guards. Otherwise, we
observed that the attackers always managed to win. This reward structure can
also be attributed to the fact that attackers in a real world scenario would like
to sneak in and wouldn’t want to shoot too often and reveal themselves to the
guards.

5 Results
We show the results for the 5 guards vs 5 attackers scenario in the FortAttack
environment.

5.1 Evolution of Strategies

Figure 3 shows the reward plot for attackers and guards and snapshots of specific
checkpoints as training progresses. The reward for guards is roughly a mirror
image of the reward for attackers as victory for one team means defeat for the
other. The rewards oscillate with multiple local extrema, i.e. maxima for one
 Natural Emergence of Multi-agent AI Strategies 23

team and a corresponding minima for the other. These extrema correspond to
increasingly complex strategies that evolve naturally - as one team gets better
at its task, it creates pressure for the other team, which in turn comes up with
a stronger and more complex strategic behavior.
1. Random behavior : At the beginning of training, agents randomly move around
and shoot in the wild. They explore trying to make sense of the FortAttack
environment and their goals in this world.
2. Flash laser : Attackers eventually learn to approach the fort and the guards
adopt a simple strategy to win. They all continuously flash their lasers cre-
ating a protection zone in front of the fort which kills any attacker that tries
to enter.
3. Sneak : As guards block entry from the front, attackers play smart. They
approach from all the directions, some of them get killed but one of them
manages to sneak in from the side.
4. Spread and flash: In response to the sneaking behavior, the guards learn to
spread out and kill all attackers before they can sneak in.
5. Deceive: To tackle the strong guards, the attackers come up with the strategy
of deception. Most of them move forward from the right while one holds back
on the left. The guards start shooting at the attackers on the right which
diverts their attention from the single attacker on the left. This attacker qui-
etly waits for the right moment to sneak in, bringing victory for the whole
team. Note that this strategy requires heterogeneous behavior amongst the
homogeneous agents, which naturally evolved without explicitly being encour-
aged to do so.
6. Spread smartly: In response to this, the guards learn to spread smartly, cov-
ering a wider region and killing attackers before they can sneak in.

5.2 Being Attentive

In each of the environment snapshots in Fig. 3 and Fig. 4, we visualize the atten-
tion paid by one alive guard to all the other agents. This guard has a dark green
dot at it’s center. All the other agents have yellow rings around them, with the
sizes of the rings being proportional to the attention values. Eg. in Fig. 4(e),
agent 1 initially paid roughly uniform and low attention to all attackers when
they were far away. Then, it started paying more attention to agent 8, which
was attacking aggressively from the right. Little did it know that it was being
deceived by the clever attackers. When agent 9 reached near the fort, agent 1
finally started paying more attention to the sneaky agent 9 but it was too late
and the attackers had successfully deceived it.

5.3 Ensemble Strategies

To train and generate strong agents, we first need strong opponents to train
against. The learnt strategies in Sect. 5.1 give us a natural way to generate
strategies from simple rules of the game. If we wish to get strong guards, we can
24 A. Deka and K. Sycara

train a single guard policy against all of the attacker strategies, by randomly
sampling one attacker strategy for each environment episode. Figure 5 shows
the reward for guards as training progresses. This time, the reward for guards
continually increases and doesn’t show an oscillating behavior.

6 Conclusions

In this work we were able to scale to multiple agents by modeling inter agent
interactions with a graph containing two attention layers. We studied the evo-
lution of complex multi agent strategies in a mixed cooperative-competitive
environment. In particular, we saw the natural emergence of deception strategy
which required heterogeneous behavior amongst homogeneous agents. If instead
we wanted to explicitly encode heterogeneous strategies, a simple extension of
our work would be to have different sets of policy parameters (fθd ) within the
same team, e.g. one set for aggressive guards and one set of defensive guards.
We believe that our study would inspire further work towards scaling multi
agent reinforcement learning to large number of agents in more complex mixed
cooperative-competitive scenarios.

References
1. Agarwal, A., Kumar, S., Sycara, K.: Learning transferable cooperative behavior in
multi-agent teams. arXiv preprint arXiv:1906.01202 (2019)
2. Al-Shedivat, M., Bansal, T., Burda, Y., Sutskever, I., Mordatch, I., Abbeel, P.:
Continuous adaptation via meta-learning in nonstationary and competitive envi-
ronments. arXiv preprint arXiv:1710.03641 (2017)
3. Baker, B., et al.: Emergent tool use from multi-agent autocurricula. arXiv preprint
arXiv:1909.07528 (2019)
4. Brockman, G., et al.: Openai gym. arXiv preprint arXiv:1606.01540 (2016)
5. Bu, L., Babu, R., De Schutter, B., et al.: A comprehensive survey of multiagent
reinforcement learning. IEEE Trans. Syst. Man Cybern. Part C (Appl. Rev.) 38(2),
156–172 (2008)
6. Haarnoja, T., Zhou, A., Abbeel, P., Levine, S.: Soft actor-critic: off-policy maxi-
mum entropy deep reinforcement learning with a stochastic actor. arXiv preprint
arXiv:1801.01290 (2018)
7. Han, L., et al.: Grid-wise control for multi-agent reinforcement learning in video
game ai. In: International Conference on Machine Learning, pp. 2576–2585 (2019)
8. Hoshen, Y.: Vain: attentional multi-agent predictive modeling. In: Advances in
Neural Information Processing Systems, pp. 2701–2711 (2017)
9. Lillicrap, T.P., et al.: Continuous control with deep reinforcement learning. arXiv
preprint arXiv:1509.02971 (2015)
10. Lowe, R., Wu, Y., Tamar, A., Harb, J., Abbeel, P., Mordatch, I.: Multi-agent
actor-critic for mixed cooperative-competitive environments. In: Neural Informa-
tion Processing Systems (NIPS) (2017)
11. Mnih, V., et al.: Human-level control through deep reinforcement learning. Nature
518(7540), 529–533 (2015)
 Natural Emergence of Multi-agent AI Strategies 25

12. Ramachandran, R.K., Preiss, J.A., Sukhatme, G.S.: Resilience by reconfiguration:

Exploiting heterogeneity in robot teams. arXiv preprint arXiv:1903.04856 (2019)
13. Rashid, T., Samvelyan, M., De Witt, C.S., Farquhar, G., Foerster, J., Whiteson, S.:
Qmix: monotonic value function factorisation for deep multi-agent reinforcement
learning. arXiv preprint arXiv:1803.11485 (2018)
14. Samvelyan, M., et al .: The starcraft multi-agent challenge. arXiv preprint
arXiv:1902.04043 (2019)
15. Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy
optimization algorithms. arXiv preprint arXiv:1707.06347 (2017)
16. Shishika, D., Paulos, J., Kumar, V.: Cooperative team strategies for multi-player
perimeter-defense games. IEEE Rob. Autom. Lett. 5(2), 2738–2745 (2020)
17. Silver, D., et al.: Mastering the game of go without human knowledge. Nature
550(7676), 354–359 (2017)
18. Sukhbaatar, S., Fergus, R., et al.: Learning multiagent communication with back-
propagation. In: Advances in Neural Information Processing Systems, pp. 2244–
2252 (2016)
19. Tampuu, A., et al.: Multiagent cooperation and competition with deep reinforce-
ment learning. PLoS one 12(4), e0172395 (2017)
20. Tan, M.: Multi-agent reinforcement learning: independent vs. cooperative agents.
In: Proceedings of the tenth International Conference on Machine Learning, pp.
330–337 (1993)
21. Vinyals, O., et al.: Starcraft ii: a new challenge for reinforcement learning. arXiv
preprint arXiv:1708.04782 (2017)
22. Watkins, C.J., Dayan, P.: Q-learning. Mach. Learn. 8(3–4), 279–292 (1992)
23. Wen, Y., Yang, Y., Luo, R., Wang, J., Pan, W.: Probabilistic recursive reasoning
for multi-agent reinforcement learning. arXiv preprint arXiv:1901.09207 (2019)
Another random document with
no related content on Scribd:
[333]

C. Hartlaub, Verhandl. Deutsch. Zool. Ges. 1896, p. 3.

[334]

Abh. Senckenb. Ges. xvi. 1891, p. 44.

[335]

This gas is frequently called air. The gas contained in the

pneumatophore of Physalia was analysed by Schloessing and
Richard, C. R. cxxii. 1896, p. 615, and found to consist of CO2, 1.7
parts, O 15.1, nitrogen and argon, 83.2.

[336]

The chemical composition of the substance here called "chitin" has

not been accurately determined. An analysis of two specimens of
Velella bladders gave 9.71 and 10.35 per cent of nitrogen, which is
higher than that of chitin and nearer to that of mucin.

[337]

Zool. Jahrb. Suppl. 1904, p. 347.

[338]

Johns Hopkins Univ. Circ. x. 1891, p. 91.

[339]

C. Chun, Abh. Senck. Nat. Ges. Frankfort, xvi. 1891.

[340]

Brooks and Conklin, Johns Hopkins Univ. Circ. x. 1891, No. 88.

[341]

C. E. Borchgrevink, "First on the Antarctic Continent," 1901, p.

227.
[342]

M. J. Delap, Irish Naturalist, x. 1901, p. 27.

[343]

E. W. L. Holt, Report on the Sea and Inland Fisheries of Ireland for

1902, pt. ii. 1903, p. xvi.

[344]

F. W. Gamble. See E. T. Browne, Proc. Roy. Irish Acad. 1900, p.

735.

[345]

Bull. Mus. Comp. Zool. xxxii. 1, 1898.

[346]

ἀκαλήφη = a nettle.

[347]

Biometrika, i. 1901, p. 90.

[348]

K. Kishinouye, Zool. Jahrb. Syst. xii. 1899, p. 206.

[349]

For the discussion of this relationship the reader is referred to

Goette, Zeitschr. wiss. Zool. lxiii. 1897, p. 360, and Carlgren, Zool.
Anz. xxii. 1899, p. 31.

[350]

See note [347], above.

[351]

E. A. Minchin, Proc. Zool. Soc. 1889, p. 583.

[352]

For good illustrations of this see Sir J. Dalyell, "Rare and

Remarkable Animals of Scotland," vol. i. 1847, pll. 13, 14, 18, 19,
20.

[353]

Archiv. Mikr. Anat. xiii. 1877, p. 795.

[354]

Agassiz and Mayer, Mem. Mus. Comp. Zool. xxvi. 3, 1902, p. 153.

[355]

F. S. Conant, Mem. Johns Hopkins Univ. iv. 1, 1898.

[356]

Kishinouye, Journ. Coll. Sci. Tokyo, xvii. 7, 1902.

[357]

A discussion of the classification of this order occurs in Vanhöffen,

"Acrasped. Med. d. deutschen Tiefsee Expedition," iii. 1902, p. 49.

[358]

The Periphyllidae constitute Haeckel's order Peromedusae.

[359]

A stage in development before the formation of the sub-umbrellar

cavity, but subsequent to the formation of the first tentacles, is
regarded as homologous with the Scyphistoma stage of other
Scyphozoa.

[360]

"Siboga" Exped. Mon. xi. 1903.

[361]
Proc. Roy. Irish Acad. 3rd ser. v. 1900, p. 735.

[362]

Cf. Darwin, Voyage of the Beagle, chap. v.

[363]

Hickson, K. Akad. Wet. Amsterdam, 1905.

[364]

J. H. Ashworth, Proc. Roy. Soc. lxiii. 1898, p. 443.

[365]

Quart. Journ. Micr. Sci. xli. 1899, p. 521.

[366]

Quoted by Hickson, Marine Investigations, S. Africa, iii. 1904, p.

215.

[367]

G. C. Bourne, Phil. Trans. Roy. Soc. clxxxvi. 1895, B. p. 464.

[368]

Quoted by Marshall, Oban Pennatulida, 1882, p. 49.

[369]

Quart. Journ. Micr. Sci. xlix. 1905, p. 327.

[370]

Corallium nobile appears to be the exception to this rule, as it is

stated that colonies and even individual zooids are occasionally
hermaphrodite. Lacaze Duthiers, "Hist. Nat. du Corail," 1864, p.
127.

[371]
G. Lindström, Handl. k. Svensk. Vet. Akad. xxxii. 1899.

[372]

J. W. Gregory, Proc. Roy. Soc. lxvi. 1899, p. 291.

[373]

G. C. Bourne, Lankester's Treatise on Zoology, pt. ii. 1900,

"Anthozoa," p. 26.

[374]

E. M. Pratt, Fauna and Geogr. Maldive Archip. ii. pt. i. 1903, p.

516.

[375]

Zool. Anz. xxix. 1905, p. 263.

[376]

S. J. Hickson, Fauna and Geog. Maldive Archip. ii. pt. i. 1903, p.

495.

[377]

Hickson, K. Akad. Wet. Amsterdam, 1905.

[378]

Journ. Imp. Fish. Bureau, Tokyo, xiv. 1, 1904.

[379]

Kitahara, Journ. Imp. Fish. Bureau, Tokyo, xiii. 3, 1904.

[380]

Johnson, Proc. Zool. Soc. 1899, p. 57.

[381]

Hickson, Nature, lxxiii. 1905, p. 5.

[382]

Moroff, Zool. Jahrb. Syst. xvii. 1902, p. 404.

[383]

Ridley, Proc. Zool. Soc. 1882, p. 231.

[384]

For a revision of this family, see Versluys, Siboga Expeditie, xii.

1902.

[385]

Jungersen (Danish Ingolf Expedition, Pennatulida, 1904) has

shown that this is the correct nomenclature of the regions of the
rachis. Nearly all other authors describe the dorsal side as ventral
and the ventral as dorsal.

[386]

S. J. Hickson, Report British Association (Southport Meeting),

1903, p. 688.

[387]

Marshall, Trans. Roy. Soc. Edinb. xxxii. 1883, p. 143.

[388]

Rumphius, Amboinsche Rariteitkamer, 1741, p. 64.

[389]

Darwin, Naturalist's Voyage round the World, 1845, p. 99.

[390]

To be described in the forthcoming Report on the Pennatulidae of

the "Siboga" Expedition.

[391]
Zool. Anz. xxv. 1902, p. 302.

[392]

Faurot, Arch. Zool. Expér. 3rd ser. iii. 1895, p. 71.

[393]

Duerden, Mem. Acad. Washington, 3rd Ser. viii. 1902.

[394]

Duerden, l.c. p. 436.

[395]

M‘Intosh, "The Marine Invertebrates and Fishes of St. Andrews,"

1875, pp. 37, 38.

[396]

M‘Intosh, "The Resources of the Sea," 1899, pp. 10, 129.

[397]

H. Prouho, Arch. Zool. Expér. 2nd ser. ix. 1891, p. 247.

[398]

Duerden, Mem. Acad. Washington, viii. 1902, p. 437.

[399]

Ashworth and Annandale, Proc. Roy. Soc. Edinb. xxv. 1904, p. 11.

[400]

For recent experiments on this case, see a forthcoming paper by

J. E. Duerden (P.Z.S.).

[401]

Saville Kent, "Great Barrier Reef," London, 1893, p. 145.

[402]

O. Carlgren, Biolog. Centralbl. xxi. 1901, p. 480.

[403]

Saville Kent, "The Great Barrier Reef," 1893, p. 144.

[404]

A. C. Haddon, Trans. Roy. Dubl. Soc. iv. 1889, p. 325.

[405]

G. H. Fowler, Quart. Journ. Micr. Sci. xxix. 1888, p. 143.

[406]

For a general account of the Madreporarian skeleton, cf. Ogilvie,

Phil. Trans. Roy. Soc. clxxxvii. B. 1896.

[407]

H. M. Bernard, Ann. Mag. Nat. Hist. (7) xiii. 1904, p. 1.

[408]

"Report on the Results of Dredging on the Macclesfield Bank,"

Admiralty Report, 1894.

[409]

C. Darwin, Coral Reefs, 3rd edition, 1889, p. 125.

[410]

For the details of these borings, see "The Atoll of Funafuti," Royal
Society of London, 1904.

[411]

For further information, see J. Stanley Gardiner, The Fauna and

Geography of the Maldive and Laccadive-Archipelagoes, vol. i. pt.
ii. 1902, p. 172.

[412]

Saville Kent, "Great Barrier Reef," 1893, p. 185.

[413]

Duerden, Mem. Ac. Washington, viii. 1902, p. 550.

[414]

H. M. Bernard, Journ. Linn. Soc. Zool. xxvi. 1897, p. 495.

[415]

E. M. Pratt, Willey's Zoological Results, pt. v. 1900, p. 591.

[416]

G. H. Fowler, Quart. Journ. Micr. Sci. xxx. 1890, p. 410.

[417]

J. E. Duerden, Mem. Ac. Washington, viii. 1902, p. 553.

[418]

M. Ogilvie, Trans. Roy. Soc. clxxxvii. B. 1896.

[419]

"The Coral Siderastraea," Carnegie Inst. No. 20, Washington,

1904.

[420]

The reader is referred to the excellent photographs of living

Fungias in Saville Kent's "Great Barrier Reef," 1893, pl. xxiv. p.
160.

[421]

Trans. Roy. Soc. Dubl. (2) vi. 1898, p. 331.

[422]

F. J. Bell, Trans. Zool. Soc. xiii. pt. ii. 1891, p. 87.

[423]

J. E. Duerden, Ann. Mag. Nat. Hist. (7) ix. 1902, p. 381.

[424]

Hickson, Nature, lxxiii. 1905, p. 5.

[425]
L. Roule, Bull. Mus. Océanogr. Monaco, 1904, p. 3.

[426]

E. van Beneden, Les Anthozoaires de la Plankton Expédition, Kiel,

1898.

[427]

A. W. Peters, Journ. Exper. Zool. ii. (1) 1905, p. 103.

[428]

Cnidoblasts are stated by Chun to occur on the tentacles of

Euchlora; and batteries of "nettle cells" by Abbott on the tentacles
of Coeloplana.

[429]

The two costae that are seen in the middle when the Ctenophore
is viewed in the transverse plane, as in Figs. 180 and 181, and the
corresponding costae on the opposite side are called the
"transverse" costae; the other four are called the "sagittal" costae.

[430]

F. Mosser, "Ctenophoren de Siboga Expedition," Leiden, 1903.

[431]

H. B. Bigelow, Bull. Mus. Comp. Zool. xxxix. 1904, p. 267.

[432]

Quart. Journ. Micr. Sci. xxxix. 1897, p. 323.

[433]

Annot. Zoolog. Japon. iv. pt. iv. 1902, p. 103.

[434]

Abbott, l.c. p. 106.

[435]

Zool. Anz. xxvii. 1904, p. 223.

[436]

The name seems first to have been used by Klein in 1734,

"Naturalis dispositio Echinodermatum" (Danzig). Leuckart about
1850 first established Echinodermata as a primary division of the
animal kingdom.

[437]

In the Synaptidae the radial canals although present in the young

are lost in the adult (Ludwig, 1892, in Bronn's Thier-Reich, Bd. ii.
Abt. 3, Buch i. p. 460).

[438]

Ludwig, loc. cit. p. 357.

[439]

This classification is substantially that suggested by Jeffrey Bell,

Catalogue of British Echinoderms in the British Museum, 1892,
except that Bell separates Holothuroidea from all others. Reasons
will be given later for regarding Holothuroidea as modified
Echinoidea.

[440]

Gr. ἀστήρ, a "star"; εἶδος, "form." Linnaeus established the genus

Asterias in 1766. Johannes Müller in 1842 used the name
"Asteriden," and in System der Asteriden, 1842, by Müller and
Troschel, the foundation of our knowledge of the group was laid.

[441]

Uexküll, "Die Physiologie der Pedicellarien," Zeitschr. f. Biol. xxxvii.

1899, p. 356.

[442]
Durham, "Wandering Cells in Echinodermata," Quart. J. Micr. Sci.
xxxiii. 1891, pp. 81 et seq.

[443]

Starfish are most destructive on oyster-beds, and hence possess

considerable negative economic value.

[444]

Mitth. des deutschen Seefischervereins, xii. 1896, p. 102, and J.

Mar. Biol. Ass. iv. 1895-97, p. 266.

[445]

Romanes, "Jellyfish, Starfish, and Sea Urchins," Intern. Scientific

Series, 1885, pp. 320, 321; Preyer, "Bewegungen von Stelleriden,"
Mitth. Zool. Stat. Neapel, vii. 1886-87, p. 22.

[446]

Preyer, loc. cit. p. 49.

[447]

Bronn's Thier-Reich, Bd. ii. Abt. 3, Buch ii. Seesterne, p. 617.

[448]

Beiträge zur Histologie der Echinodermen, Jena, 1889. Such

spaces are always to be seen in Asterina gibbosa when preserved
with corrosive sublimate or other acid reagents, but are absent
when it is preserved with osmic acid and Mueller's fluid. Though
corrosive sublimate is usually regarded as a neutral salt, its
aqueous solution decomposes with the production of a certain
amount of free hydrochloric acid.

[449]

"Beiträge zur Anatomie der Asteriden," Zeitschr. wiss. Zool. xxx.

1877, pp. 122 et seq.
[450]

"Cont. à l'Étude anat. des Astérides," Arch. Zool. Exp. (2) v. bis,
1887, p. 104.

[451]

The analogy of Echinoidea (see p. 529) might suggest that, like

the lacteals in man, these strands were channels along which the
products of digestion diffused outward. No connexion, however,
between the oral ring and the alimentary canal has been made
out, nor do there appear to be such strands developed in the
proximity of the wall of the digestive tube. A connexion between
the aboral ring and the rectum through a mesenteric cord has
been asserted, but this is doubtful.

[452]

"Die Echinodermen des Golfes von Neapel," Fauna u. Flora G. von

Neapel, xxiv. Monogr. 1897, pp. 349-351.

[453]

Ludwig, "Die Echinodermen des Golfes von Neapel," pp. 68, 69.

[454]

Ludwig, "Scientific Results of the Expedition of the 'Albatross' to

the Tropical Pacific"—"Asteroidea," 1905, pp. 91, 103.

[455]

Rés. sci. Expéd. Travailleur et Talisman, "Échinodermes," 1894,

pp. 10-15.

[456]

Schiemenz (reference on p. 440 n.).

[457]

This fact was discovered by Dr. E. J. Allen, Director of the

Plymouth Biological Station, who pointed it out to the author during
the latter's sojourn at the station in 1899.

[458]

This figure does not show the animal's attitude during forward
progression quite correctly. The tips of the two anterior arms
should be bent outwards, not inwards as in the figure.

[459]

In the more primitive Ophiuroidea (Streptophiurae) it persists all

over the body; in Cladophiurae it is found on the central part of the
disc.

[460]

How far this form of respiratory mechanism is distributed amongst

Ophiurids it is impossible to say. It was first observed by me in the
case of Ophiothrix fragilis at Plymouth in 1905, but since then I
have found it in Ophiura ciliaris and in Amphiura squamata.

[461]

"Neue Beitr. zur Anat. d. Ophiuriden," Zeitschr. wiss. Zool. xxxiv.

1880, p. 340.

[462]

"Bewegungen d. Seesternen," Mitth. Zool. Stat. Neapel, vii. 1886-

87, p. 123.

[463]

Bell, "Contribution to the Classification of Ophiuroids," Proc. Zool.

Soc. 1892, p. 175.

[464]

Hamann, Bronn's Thier-Reich, Bd. ii. Abt. 3, Ophiuroidea, 1900, p.

910 f., discriminates a family Ophiodermatidae, but gives no
character by which it can be distinguished from Ophiolepididae.
[465]

Forbes, "A History of British Starfishes and other animals of the

class Echinodermata," 1841, p. 23.

[466]

Simroth, "Anatomie und Schizogonie der Ophiactis virens,"

Zeitschr. wiss. Zool. xxvii. 1876, p. 452.

[467]

Cuénot, "Études Morphologiques sur les Echinodermes," Arch.

Biologie, xi. 1891, pp. 568 et seq.

[468]

This type of mouth-frame is represented in Fig. 215, A, by a figure

of Ophioscolex, which belongs to the Streptophiurae.

[469]

"Asteriden und Ophiuriden aus dem Silur Böhmens," Zeitschr. der

deutschen geol. Ges. lv. 1903, pp. 106-113 (Protokolle).

[470]

Geol. Magazine, No. 490, April 1905, pp. 161-168.

[471]

"Die Physiologie des Seeigelstachels," Zeitschr. für Biol. xxxix.

1900, pp. 73 et seq.

[472]

Uexküll, "Die Physiologie der Pedicellarien," Zeitschr. für Biol.

xxxvii. 1899, p. 334.

[473]

"Du rôle des pédicellaires gemmiformes des Oursins," Compt.

Rend. Acad. de Paris, cxi. 1890, pp. 62-64.
[474]

"The Fauna and Bottom Deposits near the thirty-fathom line from
the Eddystone grounds to Startpoint," Journ. Marine Biol. Ass. v.
1899, p. 472.

[475]

"Mitth. über die zool. Stat. v. Neapel," Zeitschr. wiss. Zool. xxv.
1875, p. 471.

[476]

Cuénot, "Études Morphologiques sur les Échinodermes," Arch.

Biol. xi. 1891, p. 544.

[477]

"Jellyfish, Starfish, and Sea-urchins," Intern. Sci. Series, 1885, p.

302 et seq.

[478]

"Die Physiologie des Seeigelstachels," Zeitschr. für Biol. xxxix. p.

73.

[479]

"Bewegungen von Stelleriden," Mitth. Zool. Stat. Neapel, vii. 1886-

7, p. 22.

[480]

Loc. cit.

[481]

See note on p. 541.

[482]

"Die Wirkung von Licht und Schatten auf die Seeigel," Zeitschr. für
Biol. xl. 1900, p. 447.
[483]

In the aberrant genus Asthenosoma, where there are internal

radial muscles, there is also an internal series of nerve-cells on the
radial cord.

[484]

We prefer the term "compasses," to avoid confusion with the other

meanings of the word "radius."

[485]

"Ueber die Function der Polischen Blasen am Kauapparat der

regulären Seeigel," Mitth. Zool. Stat. Neapel, xii. 1897, p. 464.

[486]

Ergebnisse naturwissenschaftlicher Forschungen auf Ceylon,

1887-1888, Bd. i. Heft 3, pp. 105 et seq.

[487]

"Das angebliche Excretionsorgan der Seeigel," Zeitschr. wiss.

Zool. lv. 1893, p. 585.

[488]

In this case the fluid flows from the lantern coelom into Stewart's
organs and vice versa. Oxygen must be absorbed through the
peristome. The Cidaridae are not as sensitive to want of oxygen as
the other families (Uexküll, loc. cit.).

[489]

Danish Ingolf Expedition, "Echinoidea," pt. i. 1903.

[490]

Prouho, "Recherches sur le Dorocidaris papillata et quelques

autres Échinides de la Méditerranée," Arch. Zool. Exp. (2) v. 1887,
p. 308.
[491]

"Revision of the Echini," Illustrated Catalogue of Museum of Comp.

Zool. Harvard, No. 7, 1874, p. 423.

[492]

British Museum Catalogue, "British Echinoderms," 1892, p. 30.

[493]

Loc. cit.

[494]

Loc. cit.

[495]

Reference on p. 528 n.

[496]

This account of the periproct is different from that ordinarily given.

It is based on the most recent examination of this family—Agassiz,
"Panamic Deep-sea Echini," Mem. Mus. Comp. Zool. xxxi. 1904, p.
36.

[497]

"Der Schatten als Reiz für Centrostephanus longispinus," Zeitschr.

für Biol. xxxiv. 1896, p. 319.

[498]

Reference on p. 532, note [489].

[499]

Mr. E. W. L. Holt, Scientific Adviser to the Irish Board of Fisheries,

casts doubt (in litt.) on much of this supposed excavation. While
disclaiming any novelty in this observation, he points out that in
many cases one side of the cavity is formed by calcareous algae,
and it seems as if the animal wanders into a crevice, in which it is
imprisoned by the growth of this plant.

[500]

These statements are based on the author's observations of the

animal in the Bay of Fundy in 1900.

[501]

Lovén, "On a recent Form of Echinoconidae," Bih. Svenska Akad.

Hand. xiii. Af. 4, No. 10, 1889.

[502]

Details were given to the author in conversation with Dr. Robertson

in 1896.

[503]

This family includes three families discriminated by Meissner

(Bronn's Thier-Reich, vol. ii. Abt. 3, Buch iv. "Die Seeigel," 1904, p.
402), viz.: Ananchytidae, Pourtalesiidae, and Urechinidae. They
only differ in the pores for the tube-feet, which are paired in the
first, slit-like and single in the second, and single in the third.

[504]

"On Silurian Echinoidea and Ophiuroidea," Quart. Journ. Geol.

Soc. lv. 1899, pp. 701 et seq.

[505]

"The Metamorphosis of Echinoderms," Quart. J. Micr. Sci. xxxviii.

1896, p. 53.

[506]

Pelagothuria is said to have no calcifications.

[507]