An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem

Bin Xin; Shiqing Liu; Zhihong Peng; Guanqiang Gao

doi:10.1109/SMC.2018.00140

An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem

Bin Xin
, Shiqing Liu
, Zhihong Peng
, Guanqiang Gao

Beijing Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

12 Citations (Scopus)

Abstract

Multi-Point Dynamic Aggregation (MPDA) is a novel task model for describing the process of multiple robots performing time-variant tasks. In the MPDA problem, several task points are located in different places and their states change over time. Multiple robots aggregate to these task points and execute the tasks cooperatively to make the states of all the task points change to zero. The task planning of MPDA is a typical NP-hard combinatorial optimization problem. Estimation of Distribution Algorithms (EDA) are evolutionary techniques based on probabilistic models. In this paper, a permutation-based EDA is proposed to solve the task planning problems in MPDA. The algorithm uses K-means clustering to update its probabilistic model which follows the multi-modal Gaussian distribution. Experimental results show that the proposed algorithm outperforms other compared methods in solving the task planning problems of MPDA.

Original language	English
Title of host publication	Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	775-780
Number of pages	6
ISBN (Electronic)	9781538666500
DOIs	https://doi.org/10.1109/SMC.2018.00140
Publication status	Published - 2 Jul 2018
Externally published	Yes
Event	2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018 - Miyazaki, Japan Duration: 7 Oct 2018 → 10 Oct 2018

Publication series

Name	Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018

Conference

Conference	2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018
Country/Territory	Japan
City	Miyazaki
Period	7/10/18 → 10/10/18

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 3 Good Health and Well-being

Access to Document

10.1109/SMC.2018.00140

Cite this

Xin, B., Liu, S., Peng, Z., & Gao, G. (2018). An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem. In Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018 (pp. 775-780). Article 8616136 (Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SMC.2018.00140

Xin, Bin ; Liu, Shiqing ; Peng, Zhihong et al. / An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem. Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 775-780 (Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018).

@inproceedings{0ec65a1ebc054a5cb9431e84d33f6c04,

title = "An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem",

abstract = "Multi-Point Dynamic Aggregation (MPDA) is a novel task model for describing the process of multiple robots performing time-variant tasks. In the MPDA problem, several task points are located in different places and their states change over time. Multiple robots aggregate to these task points and execute the tasks cooperatively to make the states of all the task points change to zero. The task planning of MPDA is a typical NP-hard combinatorial optimization problem. Estimation of Distribution Algorithms (EDA) are evolutionary techniques based on probabilistic models. In this paper, a permutation-based EDA is proposed to solve the task planning problems in MPDA. The algorithm uses K-means clustering to update its probabilistic model which follows the multi-modal Gaussian distribution. Experimental results show that the proposed algorithm outperforms other compared methods in solving the task planning problems of MPDA.",

author = "Bin Xin and Shiqing Liu and Zhihong Peng and Guanqiang Gao",

note = "Publisher Copyright: {\textcopyright} 2018 IEEE.; 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018 ; Conference date: 07-10-2018 Through 10-10-2018",

year = "2018",

month = jul,

day = "2",

doi = "10.1109/SMC.2018.00140",

language = "English",

series = "Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "775--780",

booktitle = "Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018",

address = "United States",

}

Xin, B, Liu, S, Peng, Z & Gao, G 2018, An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem. in Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018., 8616136, Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018, Institute of Electrical and Electronics Engineers Inc., pp. 775-780, 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018, Miyazaki, Japan, 7/10/18. https://doi.org/10.1109/SMC.2018.00140

An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem. / Xin, Bin; Liu, Shiqing; Peng, Zhihong et al.
Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018. Institute of Electrical and Electronics Engineers Inc., 2018. p. 775-780 8616136 (Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem

AU - Xin, Bin

AU - Liu, Shiqing

AU - Peng, Zhihong

AU - Gao, Guanqiang

PY - 2018/7/2

Y1 - 2018/7/2

N2 - Multi-Point Dynamic Aggregation (MPDA) is a novel task model for describing the process of multiple robots performing time-variant tasks. In the MPDA problem, several task points are located in different places and their states change over time. Multiple robots aggregate to these task points and execute the tasks cooperatively to make the states of all the task points change to zero. The task planning of MPDA is a typical NP-hard combinatorial optimization problem. Estimation of Distribution Algorithms (EDA) are evolutionary techniques based on probabilistic models. In this paper, a permutation-based EDA is proposed to solve the task planning problems in MPDA. The algorithm uses K-means clustering to update its probabilistic model which follows the multi-modal Gaussian distribution. Experimental results show that the proposed algorithm outperforms other compared methods in solving the task planning problems of MPDA.

AB - Multi-Point Dynamic Aggregation (MPDA) is a novel task model for describing the process of multiple robots performing time-variant tasks. In the MPDA problem, several task points are located in different places and their states change over time. Multiple robots aggregate to these task points and execute the tasks cooperatively to make the states of all the task points change to zero. The task planning of MPDA is a typical NP-hard combinatorial optimization problem. Estimation of Distribution Algorithms (EDA) are evolutionary techniques based on probabilistic models. In this paper, a permutation-based EDA is proposed to solve the task planning problems in MPDA. The algorithm uses K-means clustering to update its probabilistic model which follows the multi-modal Gaussian distribution. Experimental results show that the proposed algorithm outperforms other compared methods in solving the task planning problems of MPDA.

UR - https://www.scopus.com/pages/publications/85062212931

U2 - 10.1109/SMC.2018.00140

DO - 10.1109/SMC.2018.00140

M3 - Conference contribution

AN - SCOPUS:85062212931

T3 - Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018

SP - 775

EP - 780

BT - Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018

Y2 - 7 October 2018 through 10 October 2018

ER -

Xin B, Liu S, Peng Z, Gao G. An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem. In Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 775-780. 8616136. (Proceedings - 2018 IEEE International Conference on Systems, Man, and Cybernetics, SMC 2018). doi: 10.1109/SMC.2018.00140

An Estimation of Distribution Algorithm for Multi-robot Multi-point Dynamic Aggregation Problem

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this