Tytuł pozycji:
On transformation of conditional, conformant and parallel planning to linear programming
Classical planning in Artificial Intelligence is a computationally expensive problem of finding a sequence of actions that transforms a given initial state of the problem to a desired goal situation. Lack of information about the initial state leads to conditional and conformant planning that is more difficult than classical one. A parallel plan is the plan in which some actions can be executed in parallel, usually leading to decrease of the plan execution time but increase of the difficulty of finding the plan. This paper is focused on three planning problems which are computationally difficult: conditional, conformant and parallel conformant. To avoid these difficulties a set of transformations to Linear Programming Problem (LPP), illustrated by examples, is proposed. The results show that solving LPP corresponding to the planning problem can be computationally easier than solving the planning problem by exploring the problem state space. The cost is that not always the LPP solution can be interpreted directly as a plan.
1. The work of Adam Galuszka was supported by the SUT grant No 02/060/RGP20/0019. The work of Eryka Probierz was supported in part by the European Union through the European Social Fund as a scholarship under Grant POWR.03.02.00-00-I029, and in part by the Silesian University of Technology (SUT) through the subsidy for maintaining and developing the research potential grant in 2021 for young researchers in analysis. This work was supported by Upper Silesian Centre for Computational Science and Engineering (GeCONiI) through The National Centre for Research and Development (NCBiR) under Grant POIG.02.03.01-24-099/13. Partial results of the first author have been presented on conferences: Methods and Models in Automation and Robotics in 2015 and European Simulation Multiconference in 2018.
2. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).
