Premium
Scalable and optimal planning based on Pregel
Author(s) -
Jiang Zhihua,
Rao Dongning
Publication year - 2018
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4966
Subject(s) - scalability , computer science , cloud computing , graph , plan (archaeology) , spark (programming language) , computation , capacity planning , automated planning and scheduling , distributed computing , theoretical computer science , artificial intelligence , database , algorithm , archaeology , history , programming language , operating system
Summary Automated planning generates plans for specific tasks. Optimal planning aims at generating optimal plans under global constraints. As a result, the divide‐and‐conquer method is not applicable for optimal planning. Therefore, engineering applications of optimal planning face the scalability issue. Fortunately, cloud computing tools are on the shelf. For example, the Apache Spark is an engine for big data processing. It supports the Pregel for scalable computing. Therefore, we proposed an optimal Planning method based on the Pregel, called the PbP. Unlike classical planning, the PbP method uses the Pregel as the computation model, instead of the traditional state‐space searching. The core idea is to transform planning problems into graph processing problems. Specifically, actions are mapped into vertices, partial orders between actions are mapped into edges between vertices, and states are mapped into messages. Furthermore, the planning is viewed as message propagating in the graph, and plan traces are stored as attributes of vertices. Experimental results showed the feasibility of the proposed method PbP. Moreover, compared with state‐of‐the‐art optimal planners, our approach is more scalable and faster.