{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,4,18]],"date-time":"2023-04-18T09:14:18Z","timestamp":1681809258091},"reference-count":15,"publisher":"Walter de Gruyter GmbH","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,9,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Many systems like manufacturing systems, biological processes and even stock markets can be seen as networks of coupled decision makers and thus be described as networked discrete event systems (DES) or multi-agent discrete event systems (MADES). Information interchange between agents is usually performed indirectly via competition for shared resources. The problem of trajectory planning for MADES is about finding an optimal sequence of decisions for the particular agents. The planning process can be performed in a distributed manner. To encode the trajectory planning problem, we utilize Petri net models and present a formal way to derive integer linear programs (ILPs) that exhibit a bordered block-diagonal structure. We apply Dantzig\u2019s decomposition method to decompose the LP-relaxed problem into multiple subproblems that can be solved locally by their corresponding agents. In general, the obtained LP solutions are non-integer. Therefore, we ensure feasibility to the original ILP using a superior Branch-and-Bound algorithm. Hence, we end up with a so called Branch-and-Price algorithm, tailored to solve trajectory planning problems for general MADES via distributed optimization.<\/jats:p>","DOI":"10.1515\/auto-2018-0127","type":"journal-article","created":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T09:02:31Z","timestamp":1570006951000},"page":"751-761","source":"Crossref","is-referenced-by-count":0,"title":["Distributed trajectory planning for multi-agent discrete event systems"],"prefix":"10.1515","volume":"67","author":[{"given":"Marcus","family":"Appel","sequence":"first","affiliation":[{"name":"TU Darmstadt , Department of Control Systems and Mechatronics , Darmstadt , Germany"}]},{"given":"Michael","family":"Walther","sequence":"additional","affiliation":[{"name":"Robert Bosch GmbH , Renningen , Germany"}]},{"given":"Ulrich","family":"Konigorski","sequence":"additional","affiliation":[{"name":"TU Darmstadt , Department of Control Systems and Mechatronics , Darmstadt , Germany"}]}],"member":"374","published-online":{"date-parts":[[2019,9,13]]},"reference":[{"key":"2023041808414253620_j_auto-2018-0127_ref_001","unstructured":"R.\u2009I. Brafman and C. Domshlak. \u201cFrom One to Many: Planning for Loosely Coupled Multi-Agent Systems.\u201d In: ICAPS. Ed. by J. Rintanen et al. AAAI, 2008, pp.\u200928\u201335."},{"key":"2023041808414253620_j_auto-2018-0127_ref_002","doi-asserted-by":"crossref","unstructured":"J.\u2009R. Celaya, A.\u2009A. Desrochers and R.\u2009J. Graves. \u201cModeling and analysis of multi-agent systems using petri nets.\u201d In: 2007 IEEE International Conference on Systems, Man and Cybernetics. Oct. 2007, pp.\u20091439\u20131444.","DOI":"10.1109\/ICSMC.2007.4413960"},{"key":"2023041808414253620_j_auto-2018-0127_ref_003","unstructured":"G. Dantzig and M. Thapa. Linear Programming 2: Theory and Extensions. Springer Series in Operations Research and Financial Engineering. Springer New York, 2006."},{"key":"2023041808414253620_j_auto-2018-0127_ref_004","doi-asserted-by":"crossref","unstructured":"E. Fabre and L. Jezequel. \u201cDistributed optimal planning: an approach by weighted automata calculus.\u201d In: Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference. Dec. 2009, pp.\u2009211\u2013216.","DOI":"10.1109\/CDC.2009.5400084"},{"key":"2023041808414253620_j_auto-2018-0127_ref_005","doi-asserted-by":"crossref","unstructured":"R.\u2009E. Fikes and N.\u2009J. Nilsson. \u201cSTRIPS: A new Approach to the Application of Theorem Proving to Problem Solving.\u201d In: Artificial Intelligence 2 (1971), p.\u2009189.","DOI":"10.1016\/0004-3702(71)90010-5"},{"key":"2023041808414253620_j_auto-2018-0127_ref_006","doi-asserted-by":"crossref","unstructured":"G. Gamrath and M.\u2009E. L\u00fcbbecke. \u201cExperiments with a Generic Dantzig-Wolfe Decomposition for Integer Programs.\u201d In: Experimental Algorithms: 9th International Symposium, SEA 2010, Ischia Island, Naples, Italy, May 20\u201322, 2010. Proceedings. Ed. by P. Festa. Berlin, Heidelberg: Springer Berlin Heidelberg, 2010, pp.\u2009239\u2013252.","DOI":"10.1007\/978-3-642-13193-6_21"},{"key":"2023041808414253620_j_auto-2018-0127_ref_007","doi-asserted-by":"crossref","unstructured":"A.\u2009J. Goldman. \u201cResolution and Separation Theorems for Polyhedral Convex Sets.\u201d In: Linear Inequalities and Related Systems. Ed. by H.\u2009W. Kuhn and A.\u2009W. Tucker. Princeton University Press, 1957, pp.\u200941\u201352.","DOI":"10.1515\/9781400881987-004"},{"key":"2023041808414253620_j_auto-2018-0127_ref_008","doi-asserted-by":"crossref","unstructured":"L. Jezequel, E. Fabre and V. Khomenko. \u201cFactored Planning: From Automata to Petri Nets.\u201d In: ACM Trans. Embed. Comput. Syst. 14.2 (Feb. 2015), pp.\u200926:1\u201326:25.","DOI":"10.1145\/2656215"},{"key":"2023041808414253620_j_auto-2018-0127_ref_009","doi-asserted-by":"crossref","unstructured":"R. Kannan and P.\u2009I. Barton. \u201cConvergence-order analysis of branch-and-bound algorithms for constrained problems.\u201d In: Journal of Global Optimization 71.4 (Aug. 2018), pp.\u2009753\u2013813.","DOI":"10.1007\/s10898-017-0532-y"},{"key":"2023041808414253620_j_auto-2018-0127_ref_010","doi-asserted-by":"crossref","unstructured":"J. Lunze. Ereignisdiskrete Systeme: Modellierung und Analyse dynamischer Systeme mit Automaten, Markovketten und Petrinetzen. Oldenbourg Wissenschaftsverlag, 2012.","DOI":"10.1524\/9783486721027"},{"key":"2023041808414253620_j_auto-2018-0127_ref_011","unstructured":"S.\u2009J. Maher et al. The SCIP Optimization Suite 4.0. eng. Tech. rep.\u200917-12, Takustr.\u20097, 14195 Berlin: ZIB, 2017."},{"key":"2023041808414253620_j_auto-2018-0127_ref_012","doi-asserted-by":"crossref","unstructured":"J.\u2009W. Mamer and R.\u2009D. McBride. \u201cA Decomposition-Based Pricing Procedure for Large-Scale Linear Programs: An Application to the Linear Multicommodity Flow Problem.\u201d In: Management Science 46.5 (2000), pp.\u2009693\u2013709.","DOI":"10.1287\/mnsc.46.5.693.12042"},{"key":"2023041808414253620_j_auto-2018-0127_ref_013","unstructured":"F. Rossi, P. v. Beek and T. Walsh. Handbook of Constraint Programming (Foundations of Artificial Intelligence). New York, NY, USA: Elsevier Science Inc., 2006."},{"key":"2023041808414253620_j_auto-2018-0127_ref_014","doi-asserted-by":"crossref","unstructured":"O. Stursberg and C. Hillmann. \u201cDecentralized Optimal Control of Distributed Interdependent Automata With Priority Structure.\u201d In: IEEE Transactions on Automation Science and Engineering 14.2 (Apr. 2017), pp.\u2009785\u2013796.","DOI":"10.1109\/TASE.2017.2669893"},{"key":"2023041808414253620_j_auto-2018-0127_ref_015","doi-asserted-by":"crossref","unstructured":"M. Weerdt and B. Clement. \u201cIntroduction to planning in multiagent systems.\u201d In: Multiagent and Grid Systems 5 (Dec. 2009), pp.\u2009345\u2013355.","DOI":"10.3233\/MGS-2009-0133"}],"container-title":["at - Automatisierungstechnik"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.degruyter.com\/view\/j\/auto.2019.67.issue-9\/auto-2018-0127\/auto-2018-0127.xml","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/auto-2018-0127\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/auto-2018-0127\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,18]],"date-time":"2023-04-18T08:42:21Z","timestamp":1681807341000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.1515\/auto-2018-0127\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,1]]},"references-count":15,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2019,9,13]]},"published-print":{"date-parts":[[2019,9,25]]}},"alternative-id":["10.1515\/auto-2018-0127"],"URL":"https:\/\/doi.org\/10.1515\/auto-2018-0127","relation":{},"ISSN":["2196-677X","0178-2312"],"issn-type":[{"value":"2196-677X","type":"electronic"},{"value":"0178-2312","type":"print"}],"subject":[],"published":{"date-parts":[[2019,9,1]]}}}