CS Events

Qualifying Exam

Optimally Covering Critical Sets in R^2 with A Team of Mobile Sensing Robots


Download as iCal file

Friday, August 14, 2020, 03:00pm - 04:30pm



Siwei Feng

Location : Remote via Webex


Prof. Jingjin Yu (Advisor)

Prof. Kostas Bekris

Prof. Jie Gao

Prof. Richard Martin

Event Type: Qualifying Exam

Abstract: Optimal coverage is an important problem in robotics, e.g. for monitoring changing environments, guarding the perimeter of a building for security, detecting emergencies in an area, and so on. In this domain, we investigated several challenging variations, modelling the robots’ sensing abilities with different models (1D / 2D range sensing) and examining different types of sets to guard (1D perimeter / 2D region). Some of the problems could be optimized quite efficiently, while others are intractable to obtain optimal solutions or even to approximate within some certain ratio. Specifically, in a 1D scenario where the sets to guard are line segments and a single robot can only cover a continuous boundary segment, the maximum coverage length of a robot could be minimized quite efficiently with low polynomial time complexity. However, when the group of robots are heterogeneous, the corresponding problem of minimizing deployment costs or maximum capacity exploitation can be NP-hard to solve. When studying the problem in a 2D scenario, it is even NP-hard to approximate the minimum coverage radius within 15% to cover the boundary of a simple polygon or the simple polygon itself. Yet, it is still possible to obtain good computational results experimentally for these problems by applying some realistic assumptions or using methods as dynamic programming and integer programming.


Meeting Info: Qualifying Exam For Siwei Feng
Hosted by Siwei Feng

Friday, Aug 14, 2020 3:00 pm | 1 hour | (UTC-04:00) Eastern Time (US & Canada)

Meeting number: 120 601 5430
Password: 1234


Join by video system
Dial This email address is being protected from spambots. You need JavaScript enabled to view it.
You can also dial and enter your meeting number.

Join by phone
+1-650-429-3300 USA Toll
Access code: 120 601 5430