{"id":485,"date":"2022-12-09T07:12:06","date_gmt":"2022-12-09T07:12:06","guid":{"rendered":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/?p=485"},"modified":"2022-12-09T23:37:28","modified_gmt":"2022-12-09T23:37:28","slug":"task-allocation","status":"publish","type":"post","link":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/2022\/12\/09\/task-allocation\/","title":{"rendered":"Task Allocation"},"content":{"rendered":"\n<p>The task allocation subsystem efficiently assigns each robot tasks such that all tasks are completed in minimal time.<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table><tbody><tr><td>Inputs<\/td><td>Outputs<\/td><\/tr><tr><td>Occupancy grid map,&nbsp;<em>n<\/em>&nbsp;Robots,&nbsp;<em>m<\/em>&nbsp;Tasks, Robot positions<\/td><td>Next assigned task to robot&nbsp;<em>i<\/em><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Now that we have two types of tasks, frontier and coverage tasks, we need a task allocator that can assign each robot to these tasks and make intelligent decisions on which task will reap the most reward each assignment period. We implemented two task allocators: a naive algorithm as a baseline, and a more optimal task allocator, HIGH:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><strong>Naive Allocation<\/strong><ul><li>Greedy based on distance to task and utility<\/li><\/ul><\/li><li><strong>HIGH (Hierarchical Information Gain Heuristic) Allocation<\/strong><ul><li>Information-theoretic approach: task weight is encoded by its information gain<\/li><li>Balances exploration vs exploitation with weights based on explored area<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Each task allocator has the following two objectives: the <strong>A* path length<\/strong> to each task as the distance cost, and an additional <strong>utility<\/strong> penalty if if the task is within line-of-sight distance to an already assigned task. This prevents robots from being assigned tasks that are very close to each other in the same assignment round.<\/p>\n\n\n\n<p>HIGH uses the same costs, but additionally considers exploration of the environment vs exploitation of the already mapped areas for victim search. We are using an information-theoretic approach that weighs the naive costs, information gains, and exploration-exploitation weights to assign each robot to the task with the highest reward. We introduce two new objectives:<\/p>\n\n\n\n<div class=\"wp-block-columns is-layout-flex wp-container-core-columns-is-layout-9d6595d7 wp-block-columns-is-layout-flex\">\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:50%\">\n<ul class=\"wp-block-list\"><li><strong>Information gain<\/strong><ul><li>The information gain is [0., 1.]<\/li><li>For frontier tasks, information gain is defined as the percent of continuous unknown cells within a radius.<\/li><li>For coverage tasks, information gain is defined as the percent of free cells within a radius that have not yet been covered by the camera sensor.<\/li><li>Tasks with high information gain should be prioritized in assignment, and tasks with low information gain should be not be assigned.<\/li><\/ul><\/li><li><strong>Exploration-exploitation weight<\/strong><ul><li>When we first start the mission, we want to rapidly explore the environment. Conversely, when the environment is mostly mapped out, we want to prioritize completing coverage tasks.<\/li><li>We use a linearly decaying importance for exploration as a function of percent of area explored.<\/li><li>The total area is approximated by the user-inputted geofence area.<\/li><\/ul><\/li><\/ul>\n<\/div>\n\n\n\n<div class=\"wp-block-column is-layout-flow wp-block-column-is-layout-flow\" style=\"flex-basis:50%\">\n<figure class=\"wp-block-image size-large is-style-default\"><img loading=\"lazy\" decoding=\"async\" width=\"983\" height=\"1024\" src=\"http:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.12.01-AM-1-983x1024.png\" alt=\"\" class=\"wp-image-524\" srcset=\"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.12.01-AM-1-983x1024.png 983w, https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.12.01-AM-1-288x300.png 288w, https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.12.01-AM-1-768x800.png 768w, https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.12.01-AM-1.png 1016w\" sizes=\"auto, (max-width: 983px) 100vw, 983px\" \/><figcaption>Information Gain Heatmap<\/figcaption><\/figure>\n<\/div>\n<\/div>\n\n\n\n<p>The final HIGH objective we want to maximize is then<\/p>\n\n\n\n<p class=\"has-text-align-center\"><strong>reward_fn = (2 * utility &#8211; dist_cost) * info_gain * e2_weights<\/strong><\/p>\n\n\n\n<p>After calculating the highest priority tasks to assign next, we then optimally assign the tasks to each robot based on distance cost using the Hungarian algorithm. The total distance needed to be traveled for all robots is then minimized.<\/p>\n\n\n\n<p class=\"has-text-align-center\"><img decoding=\"async\" src=\"https:\/\/lh6.googleusercontent.com\/7dfCyCzMtE7Eu8SimtHzLSjWgzXWD7uMmw4ubbMMxvE6hqoNMRmhtGbTCOIXMv5DMY5xqR6r8508NM6-xLPoaDhN-OkejwFw2T2GLPfiNjnNFNexWsIsf4qeNsQWZCipEYCmfiry90HQHSEdcYT5cGJDGMQYDXBA4xWIo0jp0kiya0rrCBJKaogB_HJx89pK\" style=\"width: 700px\"><\/p>\n\n\n\n<p>Through both in real life and simulation testing, we found that:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>HIGH on average obtains a <strong>27% <\/strong>better SST than Naive<\/li><li>HIGH on average has a <strong>35%<\/strong> lower standard deviation of SSTs<\/li><\/ul>\n\n\n\n<figure class=\"wp-block-gallery has-nested-images columns-default is-cropped wp-block-gallery-1 is-layout-flex wp-block-gallery-is-layout-flex\">\n<figure class=\"wp-block-image size-large is-style-default\"><img loading=\"lazy\" decoding=\"async\" width=\"848\" height=\"490\" data-id=\"457\" src=\"http:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.42.10-AM-1.png\" alt=\"\" class=\"wp-image-457\" srcset=\"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.42.10-AM-1.png 848w, https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.42.10-AM-1-300x173.png 300w, https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.42.10-AM-1-768x444.png 768w\" sizes=\"auto, (max-width: 848px) 100vw, 848px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large is-style-default\"><img loading=\"lazy\" decoding=\"async\" width=\"866\" height=\"508\" data-id=\"456\" src=\"http:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.42.17-AM.png\" alt=\"\" class=\"wp-image-456\" srcset=\"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.42.17-AM.png 866w, https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.42.17-AM-300x176.png 300w, https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-content\/uploads\/sites\/59\/2022\/12\/Screenshot-2022-12-09-at-1.42.17-AM-768x451.png 768w\" sizes=\"auto, (max-width: 866px) 100vw, 866px\" \/><\/figure>\n<\/figure>\n\n\n\n<p>HIGH is significantly better than naive because:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Naive allocator does not explore the map fast enough (decides to do nearby coverage tasks)<\/li><li>Wastes too much time in low information areas<\/li><li>Lacks the \u201cbig picture\u201d view<\/li><\/ul>\n\n\n\n<p>HIGH is able to model information gain in the environment and exploit that to achieve better performance. It takes into consideration the key points that: coverage tasks which have been crossed before have low information, bigger frontiers have more information than smaller frontiers, and as search progresses information reward shifts from frontiers to coverage tasks.<\/p>\n\n\n\n<p>Additionally, the task allocation subsystem is also able to dynamically reallocate tasks. For example, if an agent runs out of battery or crashes during search, the system is able to take the unfinished tasks and reallocate them to the remaining agents such that all tasks are still completed.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The task allocation subsystem efficiently assigns each robot tasks such that all tasks are completed in minimal time. Inputs Outputs Occupancy grid map,&nbsp;n&nbsp;Robots,&nbsp;m&nbsp;Tasks, Robot positions Next assigned task to robot&nbsp;i Now that we have two types of tasks, frontier and coverage tasks, we need a task allocator that can assign each robot to these tasks<br \/><a class=\"moretag\" href=\"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/2022\/12\/09\/task-allocation\/\">+ Read More<\/a><\/p>\n","protected":false},"author":276,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9],"tags":[],"class_list":["post-485","post","type-post","status-publish","format-standard","hentry","category-fall-subsystems-subsystems"],"_links":{"self":[{"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/posts\/485","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/users\/276"}],"replies":[{"embeddable":true,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/comments?post=485"}],"version-history":[{"count":6,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/posts\/485\/revisions"}],"predecessor-version":[{"id":599,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/posts\/485\/revisions\/599"}],"wp:attachment":[{"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/media?parent=485"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/categories?post=485"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mrsdprojects.ri.cmu.edu\/2022teamf\/wp-json\/wp\/v2\/tags?post=485"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}