{"entities":{"Q1199918":{"pageid":1210667,"ns":120,"title":"Item:Q1199918","lastrevid":47115487,"modified":"2025-12-31T17:47:10Z","type":"item","id":"Q1199918","labels":{"en":{"language":"en","value":"Theory and algorithms for plan merging"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 96251"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$EC41F342-C0BB-4F8C-B50E-5418FE22B9BF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6a7c0fcb01344aa36be02cf6b4b19b12c54c8235","datavalue":{"value":{"text":"Theory and algorithms for plan merging","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1199918$12B0B2B9-665B-4E07-9835-0FF551ED8792","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c239a31328cbd74fd69ebd7292e1028fd20203b2","datavalue":{"value":"0757.68088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199918$F0B2BB35-57D9-47A7-90A7-F808F952504C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7776a3d69f346d18f288f73acd5a84ff4c7c76e0","datavalue":{"value":"10.1016/0004-3702(92)90016-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199918$C03D8561-A508-4015-90B2-D6828DB07357","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3fb1e9cca7a1682a7909354b68e136986c412d3f","datavalue":{"value":{"entity-type":"item","numeric-id":1199917,"id":"Q1199917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$F6B9CAE5-6B0E-439E-A594-9DBA3F5E06E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"95e666d41882411f9ee5a3d11cf0ad33cabba8b2","datavalue":{"value":{"entity-type":"item","numeric-id":672057,"id":"Q672057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$74243E80-FD6E-41F2-B30D-DEB75E203AA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4f7d502f76a5157c7ee09a87e3b0df5f704be87c","datavalue":{"value":{"entity-type":"item","numeric-id":204840,"id":"Q204840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$34DA3318-5A7D-4EC8-9E21-CD612C745E15","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"984e6510ec40a363d20e607cce2cc2f8b07918ae","datavalue":{"value":{"entity-type":"item","numeric-id":72340,"id":"Q72340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$0CEB5694-F64D-4303-81FE-2E4FC0ECF43C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b0879f591850b4f9f14b2c481d3e08995aa22089","datavalue":{"value":{"time":"+1993-01-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1199918$E2696A67-7D32-4259-BBF6-8AED55A8FBBD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3d055bfe8048b2bb5e4c228211df6bec1a472fb9","datavalue":{"value":"The two-fold goal of the paper is to present a formalism and a computational theory for optimal and approximate plan merging. Using the strips operator definitions, the paper proposes a formalization of the conditions under which operators in a plan can be merged. A dynamic programming algorithm is applied to obtain the optimal solution by reducing the plan merging problem to the shortest common supersequence problem (met in operation research theory). To preserve the traditional AI planning context, the paper extends the dynamic programming method to handle partially ordered plans. Since for practical (large) problems the dynamic programming technique becomes intractable, the paper proposes four approximation algorithms to compute high quality plans at low cost. Worst- and average-case complexity analyses of the approximation algorithm outputs are given, and shown that all these algorithms have linear time complexity in the number of input plan operators. Promising experimental results are exposed for the investigated heuristic methods.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199918$8318072A-99FE-427A-91E0-07117F4C17DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199918$EC1C3814-DA76-464E-B94F-5386CA0AF402","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfe779e91fe9c53ee133568259955801965765ae","datavalue":{"value":"68T05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199918$F7D1506B-5540-43F2-BD2D-AE2C11547BAC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2ec5bd897e5e5d968471ab8c440687344f86ac13","datavalue":{"value":"96251","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199918$CA924508-F7BC-4CC2-83A1-36C8476FB33B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88fdec2caa8f292c8e511a9a7f0926ee66a8b623","datavalue":{"value":"plan merging","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199918$5D1E880F-16E4-4E84-A2B5-31F8158E0848","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199918$424A7772-9B3C-4EFD-B331-58112C4D190D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0de600cf8191fa1f423fd01c9a02b172072a7391","datavalue":{"value":"approximation algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1199918$56546FCA-D617-4D2C-A78F-D2AC4BE1C95D","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"430921f5dbdf313dd3228e78017264c26e0843be","datavalue":{"value":"Q59679164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199918$0A92F46C-C4C2-43D0-86D6-EBFA8DA6498C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ddfe26001cac27b44f73ee317c958b41c5d4e225","datavalue":{"value":{"entity-type":"item","numeric-id":585901,"id":"Q585901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$6B939DEA-D75A-4726-9D7B-807A64821E7A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$B20D920F-69E4-4C79-B2D8-326E7DCD2DFF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9b213284362fd1e60bca0c733df0d74647d5092","datavalue":{"value":{"entity-type":"item","numeric-id":1101262,"id":"Q1101262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$089E42AB-7024-4A6E-BDD4-2BAD08C1EEAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$7ECDB3BA-24FC-44F6-8FE8-8C135CC859D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cb8a085292e362edfa07beae724ffbd8f286ce5","datavalue":{"value":{"entity-type":"item","numeric-id":3198904,"id":"Q3198904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$204E9FB9-38AB-4B37-957F-CDE5E5DD90C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f234ec68b7997aa22e47724a28d2902748ef614","datavalue":{"value":{"entity-type":"item","numeric-id":4954178,"id":"Q4954178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$CB5EBC0D-E523-4EBD-82A7-084E21510B3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fa95955764545a75023f8016a50f24d28c32a007","datavalue":{"value":{"entity-type":"item","numeric-id":3815511,"id":"Q3815511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$750E32E3-E349-4A0E-A6DE-E1A043A96216","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb8d1340c15324c41e85ed2951247372bdcef9c4","datavalue":{"value":{"entity-type":"item","numeric-id":4166250,"id":"Q4166250"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1199918$4968C022-D204-4636-9318-FEEFEF3DCA54","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8ad6789eee7bda2d3631cd8d4ca90ca71b75fa45","datavalue":{"value":"https://doi.org/10.1016/0004-3702(92)90016-q","type":"string"},"datatype":"url"},"type":"statement","id":"Q1199918$A478C864-8DB4-4E3E-B251-DFF6CB0B8577","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"51fb65a61794eb850e468a99bc45b48ce3d29996","datavalue":{"value":"W2068849896","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1199918$359A63DE-A579-460C-82D6-3F267B97476D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b20d672610f466cb492fc6a9937526c288a20f5d","datavalue":{"value":{"entity-type":"item","numeric-id":1402751,"id":"Q1402751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9989507a69ad853e7cc487af88a12b22049eab31","datavalue":{"value":{"amount":"+0.7598642706871033","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1199918$D8759071-FB5E-4F81-B93D-DCA7456B0CA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a69b18f5b98baf29a699921e77747c7343e139a","datavalue":{"value":{"entity-type":"item","numeric-id":3998230,"id":"Q3998230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9989507a69ad853e7cc487af88a12b22049eab31","datavalue":{"value":{"amount":"+0.7598642706871033","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1199918$8F7CD68B-26D8-43E3-AFE8-6397C7805A6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ccdebcae6861fffb0cbac0a881b4117e7304364","datavalue":{"value":{"entity-type":"item","numeric-id":1855231,"id":"Q1855231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"667a20a4ae1ba5cf25aeba6c31f4a1502dca06b7","datavalue":{"value":{"amount":"+0.7400603294372559","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1199918$E008E414-AEAB-4FFA-A933-D9F28E4C8B13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"353e1622943cf265ea2356cd7c0f82dec51c863f","datavalue":{"value":{"entity-type":"item","numeric-id":4140923,"id":"Q4140923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e2687319cbf6ce314af0a564316dd5aeb1de44b","datavalue":{"value":{"amount":"+0.7400597333908081","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1199918$FA645CAC-A5B5-43E2-841E-314AEE4E005D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e09619e98ce2c6b55939b9d25765ae05c020f37e","datavalue":{"value":{"entity-type":"item","numeric-id":3427990,"id":"Q3427990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"167bf2c3e427db1fc5099f39b8e2c8de13f89583","datavalue":{"value":{"amount":"+0.7341557741165161","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1199918$CF2A71CE-BBFF-4A07-8450-8C901100558A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1199918","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1199918"}}}}}