Birgit Engels

Papers

Total Citations

H-Index

About

Birgit Engels is a theoretical computer scientist whose work explores the computational complexity of robotic movement and swarm coordination. Her most significant contributions center on the analysis of Randolph’s Robot Game, a puzzle-inspired model for robots with minimal self-localization capabilities. In her landmark 2006 paper, "Randolphs Robot Game is NP-hard!" (12 citations), she proved that coordinating a swarm of robots under these movement constraints is computationally intractable. She followed this with "Randolph's Robot Game is NP-complete!" (3 citations), establishing the problem’s precise complexity class. These results are foundational for understanding the limits of simple, resource-constrained robotic systems—relevant to fields like distributed robotics and swarm intelligence. By bridging board game mechanics with formal complexity theory, Engels has provided a compelling framework for studying robots that move until they hit an obstacle, a model that captures real-world challenges in low-cost automation and exploration. Her work remains a touchstone for researchers investigating the inherent difficulty of planning in minimal-sensing environments.