Boundary sketching with asymptotically optimal distance and rotation. (English) Zbl 07786527
Rajsbaum, Sergio (ed.) et al., Structural information and communication complexity. 30th international colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6–9, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13892, 357-385 (2023).
Summary: We address the problem of designing a distributed algorithm for two robots that sketches the boundary of an unknown shape. Critically, we assume a certain amount of delay in how quickly our robots can react to external feedback. In particular, when a robot moves, it commits to move along path of length at least \(\lambda \), or turn an amount of radians at least \(\lambda\) for some positive \(\lambda \le 1/2^6\), that is normalized based on a unit diameter shape. Then, our algorithm outputs a polygon that is an \(\epsilon \)-sketch, for \(\epsilon = 8\sqrt{\lambda } \), in the sense that every point on the shape boundary is within distance \(\epsilon\) of the output polygon. Moreover, our costs are asymptotically optimal in two key criteria for the robots: total distance travelled and total amount of rotation.
Additionally, we implement our algorithm, and illustrate its output on some specific shapes.
For the entire collection see [Zbl 1528.68034].
Additionally, we implement our algorithm, and illustrate its output on some specific shapes.
For the entire collection see [Zbl 1528.68034].
MSC:
| 68Mxx | Computer system organization |
| 68Q11 | Communication complexity, information complexity |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Rudin, W., Principles of Mathematical Analysis (1976), New York: McGraw-Hill Education, New York · Zbl 0346.26002 |
| [2] | Dekster, BV, The length of a curve in space with curvature at most K, Am. Math. Soc., 79, 2, 271-278 (1980) · Zbl 0434.53037 |
| [3] | Munkres, J., Topology (2000), Hoboken: Prentice-Hall Pearson, Hoboken |
| [4] | Choset, H., Coverage for robotics-a survey of recent results, Ann. Math. Artif. Intell., 31, 113-126 (2001) · Zbl 1314.68317 · doi:10.1023/A:1016639210559 |
| [5] | Koenig, S.; Szymanski, B.; Liu, Y., Efficient and inefficient ant coverage methods, Ann. Math. Artif. Intell., 31, 41-76 (2001) · doi:10.1023/A:1016665115585 |
| [6] | Bruemmer, D.J., et al.: A robotic swarm for spill finding and perimeter formation. Technical report. Idaho National Engineering and Environmental Lab Idaho Falls (2002) |
| [7] | Marthaler, D., Bertozzi, A.L.: Collective motion algorithms for determining environmental boundaries. In: SIAM Conference on Applications of Dynamical Systems, pp. 1-15 (2003) |
| [8] | Kemp, M., Bertozzi, A.L., Marthaler, D.: Multi-UUV perimeter surveillance. In: Proceedings of IEEE/OES Autonomous Underwater Vehicles, pp. 102-107 (2004) |
| [9] | Marthaler, D., Bertozzi, A.L.: Tracking environmental level sets with autonomous vehicles”. In: Butenko, S., Murphey, R., Pardalos, P.M. (eds.) Recent developments in cooperative control and optimization. Cooperative Systems, vol. 3, pp. 317-332. Springer, Boston (2004). doi:10.1007/978-1-4613-0219-3_17 · Zbl 1079.93003 |
| [10] | Zhang, F., Justh, E.W., Krishnaprasad, P.S.: Boundary following using gyroscopic control. In: 2004 43rd IEEE Conference on Decision and Control (CDC) (IEEE Cat. No. 04CH37601), vol. 5, pp. 5204-5209. IEEE (2004) |
| [11] | Casbeer, DW., et al.: Forest fire monitoring with multiple small UAVs. In: 2005 Proceedings of the American Control Conference, pp. 3530-3535. IEEE (2005) |
| [12] | Clark, J., Fierro, R.: Cooperative hybrid control of robotic sensors for perimeter detection and tracking. In: 2005 Proceedings of the American Control Conference, pp. 3500-3505. IEEE (2005) |
| [13] | Casbeer, DW, Cooperative forest fire surveillance using a team of small unmanned air vehicles, Int. J. Syst. Sci., 37, 6, 351-360 (2006) · Zbl 1101.93055 · doi:10.1080/00207720500438480 |
| [14] | Spears, D.; Kerr, W.; Spears, W., Physics-based robot swarms for coverage problems, Int. J. Intell. Control Syst., 11, 3, 11-23 (2006) |
| [15] | Hsieh, MA; Kumar, V.; Chaimowicz, L., Decentralized controllers for shape generation with robotic swarms, Robotica, 26, 5, 691-701 (2008) · doi:10.1017/S0263574708004323 |
| [16] | Zhang, F., Haq, S.: Boundary following by robot formations without GPS. In: 2008 IEEE International Conference on Robotics and Automation, pp. 152-157. IEEE (2008) |
| [17] | Zhang, F.; Leonard, NE, Cooperative filters and control for cooperative exploration, IEEE Tran. Autom. Control, 55, 3, 650-663 (2010) · Zbl 1368.93736 · doi:10.1109/TAC.2009.2039240 |
| [18] | Pettersson, LH; Pozdnyakov, D., Monitoring of Harmful Algal Blooms (2013), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-540-68209-7 |
| [19] | Pressley, A., Elementary Differential Geometry (2012), London: Springer, London · Zbl 1191.53002 · doi:10.1007/978-1-84882-891-9 |
| [20] | Hoy, M., A method of boundary following by a wheeled mobile robot based on sampled range information, J. Intell. Robot. Syst., 72, 3-4, 463-482 (2013) · doi:10.1007/s10846-013-9825-7 |
| [21] | Matveev, AS; Hoy, MC; Savkin, AV, The problem of boundary following by a unicycle-like robot with rigidly mounted sensors, Robot. Auton. Syst., 61, 3, 312-327 (2013) · doi:10.1016/j.robot.2012.12.003 |
| [22] | Tokekar, P., Tracking aquatic invaders: autonomous robots for monitoring invasive fish, IEEE Robot. Autom. Mag., 20, 3, 33-41 (2013) · doi:10.1109/MRA.2012.2220506 |
| [23] | Fahad, M., et al.: Robotic simulation of dynamic plume tracking by unmanned surface vessels. In: 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 2654-2659. IEEE (2015) |
| [24] | Saldana, D., Assunção, R., Campos, Campos, M.F.: A distributed multi-robot approach for the detection and tracking of multiple dynamic anomalies. In: 2015 IEEE International Conference on Robotics and Automation (ICRA), pp. 1262-1267. IEEE (2015) |
| [25] | Goodfellow, I.; Bengio, Y.; Courville, A., Deep Learning (2016), Cambridge: The MIT Press, Cambridge · Zbl 1373.68009 |
| [26] | Chatterjee, S., Wu, W.: Cooperative curve tracking in two dimensions without explicit estimation of the field gradient. In: 2017 4th International Conference on Control, Decision and Information Technologies (CoDIT), pp. 0167-0172. IEEE (2017) |
| [27] | Nguyen, A., et al.: Using a UAV for destructive surveys of mosquito population. In: 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7812-7819. IEEE (2018) |
| [28] | Chatterjee, S., Wu, W.: A modular approach to level curve tracking with two nonholonomic mobile robots. In: International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, vol. 59292, p. V009T12A051. American Society of Mechanical Engineers (2019) |
| [29] | Al-Abri, S.; Zhang, F., A distributed active perception strategy for source seeking and level curve tracking, IEEE Trans. Autom. Control, 67, 5, 2459-2465 (2021) · Zbl 1537.93621 · doi:10.1109/TAC.2021.3077457 |
| [30] | Stanton, MC, The application of drones for mosquito larval habitat identification in rural environments: a practical approach for malaria control?, Malaria J., 20, 1, 1-17 (2021) · doi:10.1186/s12936-021-03759-2 |
| [31] | Carrasco-Escobar, G., The use of drones for mosquito surveillance and control, Parasites Vectors, 15, 1, 473 (2022) · doi:10.1186/s13071-022-05580-5 |
| [32] | Ericksen, J., Aerial survey robotics in extreme environments: mapping volcanic CO2 emissions with flocking UAVs, Front. Control Eng., 3, 7 (2022) · doi:10.3389/fcteg.2022.836720 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
