{"id":809,"date":"2020-07-30T16:42:32","date_gmt":"2020-07-30T16:42:32","guid":{"rendered":"https:\/\/asarg.hackresearch.com\/main\/?p=809"},"modified":"2020-08-04T19:23:08","modified_gmt":"2020-08-04T19:23:08","slug":"relocating-units-in-robot-swarms-with-uniform-control-signals-is-pspace-complete","status":"publish","type":"post","link":"https:\/\/asarg.hackresearch.com\/main\/2020\/07\/30\/relocating-units-in-robot-swarms-with-uniform-control-signals-is-pspace-complete\/","title":{"rendered":"Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete"},"content":{"rendered":"\n<p><strong>Title: <\/strong>Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete<\/p>\n\n\n\n<p><strong>Authors:<\/strong> <strong> <\/strong>David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie<\/p>\n\n\n\n<p><strong>Conference: <\/strong> The 32nd Canadian Conference on Computational Geometry (CCCG 2020)<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p><strong>Abstract:<\/strong> This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction on a 2D grid board with geometric obstacles. We show that the problem of deciding if a particular particle can be relocated to a specified location on the board is PSPACE-complete when only allowing 1\u00d71 particles. This shows a separation between this problem, called the relocation problem, and the occupancy problem in which we ask whether a particular location can be occupied by any particle on the board, which is known to be in P with only 1\u00d71 particles. We then consider both the occupancy and relocation problems for the case of extremely simple rectangular geometry, but slightly more complicated pieces consisting of 1\u00d72 and 2\u00d71 domino particles, and show that in both cases the problems are PSPACE-complete.<\/p>\n\n\n\n<p><strong>Virtual Talk:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"CCCG 2020: Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete\" width=\"525\" height=\"295\" src=\"https:\/\/www.youtube.com\/embed\/fcipL55UQZs?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p><\/p>\n\n\n\n<p><strong>Accompanying Videos:<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Title: Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete Authors: David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie Conference: The 32nd Canadian Conference on Computational Geometry (CCCG 2020) Abstract: This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/asarg.hackresearch.com\/main\/2020\/07\/30\/relocating-units-in-robot-swarms-with-uniform-control-signals-is-pspace-complete\/\" class=\"more-link\">Continue reading<span class=\"screen-reader-text\"> &#8220;Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete&#8221;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[4],"tags":[34,32,13],"_links":{"self":[{"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/posts\/809"}],"collection":[{"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/comments?post=809"}],"version-history":[{"count":3,"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/posts\/809\/revisions"}],"predecessor-version":[{"id":814,"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/posts\/809\/revisions\/814"}],"wp:attachment":[{"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/media?parent=809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/categories?post=809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/asarg.hackresearch.com\/main\/wp-json\/wp\/v2\/tags?post=809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}