{"id":645,"date":"2016-02-18T00:46:04","date_gmt":"2016-02-18T05:46:04","guid":{"rendered":"http:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/?page_id=645"},"modified":"2016-05-06T21:26:11","modified_gmt":"2016-05-07T01:26:11","slug":"multi-agent-planning-and-scheduling","status":"publish","type":"page","link":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/system-implementation\/multi-agent-planning-and-scheduling\/","title":{"rendered":"Multi-Agent Planner Subsystem"},"content":{"rendered":"<p>The task of the multi-agent based planner is to decide the most optimal spot and route for a parking car as soon as receives the &#8220;Park&#8221; command from the user.<\/p>\n<h2 style=\"text-align: justify\">Modified A* Algorithm Inputs<\/h2>\n<ul>\n<li><b>Available Spots<\/b>: The algorithm can use one spot and provide the best route to the spot, or can choose the best spot from a list of spots and the best route to that spot. \u00a0The option for providing only one spot allows a) the user to choose a spot for the vehicle when adding a Virtual Vehicle to the GUI or b) when the vehicle is exiting, it must be destined for the exit &#8220;spot&#8221;.<\/li>\n<li><b>Motion of Vehicles<\/b>:\u00a0One of the characteristics of this modified A* algorithm is that it plans a route to the spot that avoids the paths of other spots. \u00a0Thus, it needs to know the waypoints of all moving vehicles in order to avoid their paths.<\/li>\n<\/ul>\n<h2 style=\"text-align: justify\">Modified A* Algorithm\u00a0Implementation<\/h2>\n<ul>\n<li><b>H-Cost<\/b>:\u00a0Rather than the traditional h-cost of the distance between the current location and the parking spot (goal), this modified A* uses the distance between the current location and the\u00a0<em>exit<\/em>. \u00a0This is implemented so that parking spots closer to the exit will have lower f-scores.<\/li>\n<li><b>G-Cost<\/b>: The modified A* algorithm uses the g-cost as the sum of the distance traveled to reach the current location and an additional +2 cost for any place in the current path that overlaps the path of any other vehicle. \u00a0This is to encourage the A* planner to choose a path that has minimal overlap with other vehicles to avoid congestion.<\/li>\n<li><strong>Corner Cost<\/strong>: A +1 cost is added to each turn in the path. \u00a0This is because the Oculus Prime is prone to drift and performs better in straight line paths. \u00a0To optimize the navigation, a corner cost is added for each turn the vehicle makes to avoid paths with multiple turns.<\/li>\n<li><strong>Way-point Extraction<\/strong>: When the planner has completed the path, the way-points are extracted. \u00a0A way-point is the start location, end location, and the location of any turn the vehicle takes.<\/li>\n<li><strong>Choosing Best Spot<\/strong>: If a list of spots is sent to the planner, it will run the modified A* algorithm on the 10 spots closest to the exit. \u00a0The algorithm will return the f-score of the path and the way-points of the path. \u00a0The spot with the lowest f-score is chosen as the best spot and the way-points are then passed to the navigation stack to follow to the parking spot.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<div id=\"attachment_646\" style=\"width: 337px\" class=\"wp-caption aligncenter\"><a href=\"http:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-content\/uploads\/sites\/10\/2016\/02\/Selection_011.gif\" rel=\"attachment wp-att-646\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-646\" class=\"wp-image-646 \" src=\"http:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-content\/uploads\/sites\/10\/2016\/02\/Selection_011.gif\" alt=\"Selection_011\" width=\"327\" height=\"306\" \/><\/a><p id=\"caption-attachment-646\" class=\"wp-caption-text\">\u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 Parking Lot with Spot Numbers<\/p><\/div>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The task of the multi-agent based planner is to decide the most optimal spot and route for a parking car as soon as receives the &#8220;Park&#8221; command from the user. Modified A* Algorithm Inputs Available Spots: The algorithm can use one spot and provide the best route to the spot, or can choose the best<br \/><a class=\"moretag\" href=\"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/system-implementation\/multi-agent-planning-and-scheduling\/\">+ Read More<\/a><\/p>\n","protected":false},"author":17,"featured_media":0,"parent":84,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"template_parts\/page-fullwidth_template.php","meta":{"footnotes":""},"class_list":["post-645","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/pages\/645","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/users\/17"}],"replies":[{"embeddable":true,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/comments?post=645"}],"version-history":[{"count":7,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/pages\/645\/revisions"}],"predecessor-version":[{"id":920,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/pages\/645\/revisions\/920"}],"up":[{"embeddable":true,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/pages\/84"}],"wp:attachment":[{"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2015teami\/wp-json\/wp\/v2\/media?parent=645"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}