Concrete Planning in PlanICS Framework by Combining SMT with GEO and Simulated Annealing^*

Issue title: Concurrency, Specification, and Programming: Special Issue of Selected Papers of CS&P 2015

Guest editors: Ludwik Czaja, Wojciech Penczek and Krzysztof Stencel

Article type: Research Article

Authors: Niewiadomski, Artur^a | Skaruz, Jaroslaw^a | Switalski, Piotr^a | Penczek, Wojciech^{b; †}

Affiliations: [a] Institute of Computer Science, Siedlce University of Natural Sciences and Humanities, 3-Maja 54, 08-110 Siedlce, Poland. {artur.niewiadomski, jaroslaw.skaruz, piotr.switalski}@uph.edu.pl | [b] Institute of Computer Science, Polish Academy of Sciences, Jana Kazimierza 5, 01-248 Warsaw, Poland. penczek@ipipan.waw.pl

Correspondence: [†] Address for correspondence: Institute of Computer Science, Siedlce University of Natural Sciences and Humanities, 3-Maja 54, 08-110 Siedlce, Poland

Note: [*] This work has been supported by the National Science Centre under the grant No. 2011/01/B/ST6/01477.

Abstract: The paper deals with the concrete planning problem – a stage of the web service composition in the PlanICS framework. We present several known and new methods of concrete planning including those based on Satisfiability Modulo Theories (SMT), Genetic Algorithm (GA), as well as methods combining SMT with GA and other nature-inspired algorithms such as Simulated Annealing (SA) and Generalised Extremal Optimization (GEO). The discussion of all the approaches is supported by the complexity analysis, extensive experimental results, and illustrated by a running example.

Keywords: Web Service Composition, Concrete Planning, PlanICS, SMT, Genetic Algorithm, Hybrid Algorithm, Simulated Annealing, GEO

DOI: 10.3233/FI-2016-1409

Journal: Fundamenta Informaticae, vol. 147, no. 2-3, pp. 289-313, 2016