Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. We initiate the study of a learning-augmented variant of the classical, notoriously hard online graph exploration problem by adding access to machine-learned predictions. We propose an algorithm that naturally integrates predictions into the well-known Nearest Neighbor (NN) algorithm and significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality. We provide theoretical worst-case bounds that gracefully degrade with the prediction error, and we complement them by computational experiments that confirm our results. Further, we extend our concept to a general framework to robustify algorithms. By interpolating carefully between a given algorithm and NN, we prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs.

利用机器学习预测作为辅助，通过引入预测算法结合最近邻算法，探索未知环境的学习增加变种基于线上图探索问题的研究，证明当预测精度高时算法显著优于其他线上算法，并在预测较差时保持良好保证，提供了与预测误差平稳退化的理论最坏情况下的绑定，并通过计算实验证实了结果，同时还扩展了该概念到鲁棒算法的一般框架，通过在给定算法与最近邻算法之间进行谨慎插值，证明了新的性能边界，既利用特定输入的良好性能，又确立了对任意输入的鲁棒性。

在线图形探索方法的鲁棒化