[{"file_date_updated":"2021-09-29T12:34:47Z","language":[{"iso":"eng"}],"keyword":["Robot Exploration","Finite Automaton","Hybrid Model for Programmable Matter","Convex Hull"],"ddc":["000"],"department":[{"_id":"79"}],"user_id":"55557","_id":"25126","status":"public","file":[{"date_updated":"2021-09-29T12:34:47Z","creator":"liedtke","date_created":"2021-09-29T12:34:47Z","file_size":10114825,"access_level":"local","file_id":"25128","file_name":"Master - Thesis.pdf","content_type":"application/pdf","relation":"main_file"}],"abstract":[{"lang":"eng","text":"Motivated by the prospect of computing agents that explore unknown environments and construct convex hulls on the nanoscale, we investigate the capabilities and limitations of a single deterministic finite automaton robot in the three-dimensional hybrid model for programmable matter. In this model, active robots move on a set of passive tiles, called configuration, with the geometric shape of rhombic dodecahedra on the adjacency graph of the face-centered cubic sphere-packing. We show that the exploration problem is equally hard in the hybrid model and in three-dimensional mazes, in which tiles have the shape of cubes and are positioned at the vertices of $\\mathbb{Z}^3$. Thereby, a single robot with a constant number of pebbles cannot solve this problem in the hybrid model on arbitrary configurations. We provide algorithms for a robot with two pebbles that solve the exploration problem in the subclass of compact configurations of size $n$ in $\\O(n^3)$ rounds. Further, we investigate the robot's capabilities of detection and hull construction in terms of restricted orientation convexity. We show that a robot without any pebble can detect strong $\\O$-convexity in $\\O(n)$ rounds, but cannot detect weak $\\O$-convexity, not even if provided with a single pebble. Assuming that a robot can construct tiles from scratch and deconstruct previously constructed tiles, we show that the strong $\\O$-hull of any given configuration of size $n$ can be constructed in $\\O(n^4)$ rounds, even if the robot cannot distinguish constructed from native tiles."}],"type":"mastersthesis","title":"Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model","supervisor":[{"first_name":"Christian","id":"20792","full_name":"Scheideler, Christian","last_name":"Scheideler"}],"date_created":"2021-09-29T12:37:39Z","author":[{"last_name":"Liedtke","full_name":"Liedtke, David Jan","id":"55557","first_name":"David Jan"}],"date_updated":"2022-01-06T06:56:53Z","citation":{"ieee":"D. J. Liedtke, <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>. 2021.","chicago":"Liedtke, David Jan. <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>, 2021.","ama":"Liedtke DJ. <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>.; 2021.","apa":"Liedtke, D. J. (2021). <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>.","bibtex":"@book{Liedtke_2021, title={Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model}, author={Liedtke, David Jan}, year={2021} }","mla":"Liedtke, David Jan. <i>Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model</i>. 2021.","short":"D.J. Liedtke, Exploration and Convex Hull Construction in the Three-Dimensional Hybrid Model, 2021."},"year":"2021","has_accepted_license":"1"}]