{"id":48,"date":"2020-07-14T14:40:43","date_gmt":"2020-07-14T18:40:43","guid":{"rendered":"https:\/\/sites.bu.edu\/securingmas\/?p=48"},"modified":"2025-09-15T05:18:43","modified_gmt":"2025-09-15T09:18:43","slug":"admm-optimization-for-multi-agent-path-planning-with-spatio-temporal-constraints","status":"publish","type":"post","link":"https:\/\/sites.bu.edu\/securingmas\/2020\/07\/14\/admm-optimization-for-multi-agent-path-planning-with-spatio-temporal-constraints\/","title":{"rendered":"ADMM Optimization for Multi-agent Path Planning with Spatio-Temporal Constraints"},"content":{"rendered":"<p><img loading=\"lazy\" src=\"\/securingmas\/files\/2020\/07\/additionalConstraints-eps-converted-to-614x636.png\" alt=\"\" class=\"alignright wp-image-59\" width=\"240\" height=\"249\" srcset=\"https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/additionalConstraints-eps-converted-to-614x636.png 614w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/additionalConstraints-eps-converted-to-768x796.png 768w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/additionalConstraints-eps-converted-to-988x1024.png 988w\" sizes=\"(max-width: 240px) 100vw, 240px\" \/>As part of Thrust 2 of our project, we study novel algorithms for multi-agent path planning for continuous environments with sound but incomplete detection guarantees but that can also pursue secondary optimization objectives.<\/p>\n<h2>Path planning based on ADMM<\/h2>\n<p>We created a path planning method based on the continuous optimization Alternating Direction Method of Multipliers (ADMM)\u00a0 While ADMM is a well-studied algorithm from the optimization and machine learning literature). The resulting algorithm is very flexible, and can handle many different types of objectives and non-convex temporal-spatial constraints while allowing infeasible initializations. Although this approach can only ensure local convergence, when combined with a proper initialization, the algorithm empirically shows robust convergence, and the resulting paths have been tested on a multiagent experimental platform of iCreate robots.<\/p>\n<div style=\"width: 1920px;\" class=\"wp-video\"><!--[if lt IE 9]><script>document.createElement('video');<\/script><![endif]-->\n<video class=\"wp-video-shortcode\" id=\"video-48-1\" width=\"1920\" height=\"1080\" preload=\"metadata\" controls=\"controls\"><source type=\"video\/mp4\" src=\"\/securingmas\/files\/2020\/07\/2020-iros-admmPathPlanning.mp4?_=1\" \/><a href=\"\/securingmas\/files\/2020\/07\/2020-iros-admmPathPlanning.mp4\">\/securingmas\/files\/2020\/07\/2020-iros-admmPathPlanning.mp4<\/a><\/video><\/div>\n<p>&nbsp;<\/p>\n<h2>Ellipsoidal bounds for deviation attack constraints<\/h2>\n<p>A challenge in the application, which was previously unsolved in the literature, was to enforce constraints that guarantee that an agent does not have a feasible deviation attack. As part of this optimization method, we therefore developed a type of differentiable constraint that is based on ellipsoidal bounds.<\/p>\n<figure id=\"attachment68\" aria-describedby=\"caption-attachment68\" style=\"width: 1034px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" src=\"\/securingmas\/files\/2020\/07\/ellipsoidal-constraint-1024x318.png\" alt=\"Illustration of the ellipsoidal constraint bounding legitimate deviations from the planned trajectory from unwanted deviations.\" width=\"1024\" height=\"318\" class=\"wp-image-68 size-large\" srcset=\"https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/ellipsoidal-constraint-1024x318.png 1024w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/ellipsoidal-constraint-636x198.png 636w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/ellipsoidal-constraint-768x239.png 768w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/ellipsoidal-constraint-1536x478.png 1536w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/ellipsoidal-constraint-2048x637.png 2048w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption id=\"caption-attachment68\" class=\"wp-caption-text\">Illustration of the ellipsoidal constraint bounding legitimate deviations from the planned trajectory from unwanted deviations.<\/figcaption><\/figure>\n<p>The foci of the ellipsoid are located at co-observation points or waypoints, while the radii are determined from the maximum speed of a robot times the period elapsed between co-observations or waypoints. The ellipsoidal region represents an upper bound on the set of points that can be reached by a robot between known locations.<br \/>\n<img loading=\"lazy\" src=\"\/securingmas\/files\/2020\/07\/ellipsoid-distance-150x150.png\" alt=\"Illustration of our signed distance from an ellipsoid\" width=\"150\" height=\"150\" class=\"alignleft wp-image-67 size-thumbnail\" \/>We then proposed a definition of distance between a point or line segment and the ellipsoid that is differentiable with respect to the parameters of the ellipse. This then allows us to add constraints to the trajectories of a robot that guarantee the exclusion of a forbidden zone from the set of points potentially reachable by the robot between known or observed locations. Since the constraints are differentiable, they can be incorporated in our ADMM planner.<\/p>\n<h2>Addressing infeasibility via additions of agents<\/h2>\n<p>When applying our ADMM-based path planning algorithm, we noticed that some problems are fundamentally infeasible; for instance, in some cases, pairs of agents are too far apart and cannot move fast enough to satisfy a given co-observation constraint. In these cases, we can still obtain a partial solution with our continuous optimization framework by ignoring this constraint. We have developed an extended method that transforms such partial solutions to full solutions that satisfy our notion of security constraints by adding a minimal number of new agents. In our method, the additional agents start on the same routes of the original agents (forming sub-teams). We then find a graph containing the original trajectories together with cross-trajectory segments representing opportunities for agents to change their membership across different sub-teams.<br \/>\n<img loading=\"lazy\" src=\"\/securingmas\/files\/2020\/07\/RRT-cross-trajectory-150x150.png\" alt=\"Example of RRT tree from one point to all \" width=\"150\" height=\"150\" class=\"alignleft wp-image-70 size-thumbnail\" \/>These segments are found by using a combination of RRT* (an optimal sampling-based algorithm) and validating such solutions using the ellipsoidal constraints previously developed in this project. We then find the assignment of agents to sub-teams and cross-trajectory edges as a multi-flow network optimization problem.<\/p>\n<figure id=\"attachment71\" aria-describedby=\"caption-attachment71\" style=\"width: 646px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" src=\"\/securingmas\/files\/2020\/07\/cross-trajectory-graph-flow-e1757579083872-636x461.png\" alt=\"Example of a graph with flow that assigns extra cross-trajectory robots\" width=\"636\" height=\"461\" class=\"wp-image-71 size-medium\" srcset=\"https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/cross-trajectory-graph-flow-e1757579083872-636x461.png 636w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/cross-trajectory-graph-flow-e1757579083872-1024x743.png 1024w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/cross-trajectory-graph-flow-e1757579083872-768x557.png 768w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/cross-trajectory-graph-flow-e1757579083872.png 1070w\" sizes=\"(max-width: 636px) 100vw, 636px\" \/><figcaption id=\"caption-attachment71\" class=\"wp-caption-text\">Example of a graph with flow that assigns extra cross-trajectory robots<\/figcaption><\/figure>\n<p>Note that there always exists a trivial solution where we can secure any plan by simply adding a second agent to each trajectory (such that each agent in a pair can always check on the other); however, our optimization procedure can typically reduce the number of agents while also improving security by preferring agents that move across sub-teams as often as possible (which, from our previous distributed blocklist work, it is known to improve the resilience of the system to multiple attacks).<\/p>\n<figure id=\"attachment72\" aria-describedby=\"caption-attachment72\" style=\"width: 1034px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" src=\"\/securingmas\/files\/2020\/07\/thesis-final-044-1024x896.png\" alt=\"Path planning with additional agents: the colored paths show the routes of the additional agents identified by our graph flow solution\" width=\"1024\" height=\"896\" class=\"size-large wp-image-72\" srcset=\"https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/thesis-final-044-1024x896.png 1024w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/thesis-final-044-636x557.png 636w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/thesis-final-044-768x672.png 768w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/thesis-final-044-1536x1344.png 1536w, https:\/\/sites.bu.edu\/securingmas\/files\/2020\/07\/thesis-final-044.png 1600w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption id=\"caption-attachment72\" class=\"wp-caption-text\">Path planning with additional agents: the colored paths show the routes of the additional agents identified by our graph flow solution<\/figcaption><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>As part of Thrust 2 of our project, we study novel algorithms for multi-agent path planning for continuous environments with sound but incomplete detection guarantees but that can also pursue secondary optimization objectives. Path planning based on ADMM We created a path planning method based on the continuous optimization Alternating Direction Method of Multipliers (ADMM)\u00a0 [&hellip;]<\/p>\n","protected":false},"author":11510,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/posts\/48"}],"collection":[{"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/users\/11510"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/comments?post=48"}],"version-history":[{"count":7,"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/posts\/48\/revisions"}],"predecessor-version":[{"id":93,"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/posts\/48\/revisions\/93"}],"wp:attachment":[{"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/media?parent=48"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/categories?post=48"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.bu.edu\/securingmas\/wp-json\/wp\/v2\/tags?post=48"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}