# Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case +
## 8 Concluding Remarks  
We have presented, to our knowledge, the first asymptotically optimal, \(\mathcal{O}(1)\)-time algorithm for Complete Visibility for point robots with lights using \(\mathcal{O}(1)\) colors in the asynchronous setting with monotonic robot movements in a 2-dimensional real plane. The best previous results for this problem were \(\mathcal{O}(\log N)\) time in the fully synchronous setting and \(\mathcal{O}(1)\) time for the semi-synchronous setting, both using \(\mathcal{O}(1)\) colors. The result of this paper significantly improves on these existing results through new techniques as the asynchronous setting is the weakest and fully synchronous setting is the strongest among the three settings, fully synchronous, semi-synchronous, and asynchronous. The Complete Visibility problem is fundamental with application in solving other problems under obstructed visibility. For example, the solution presented in this paper already played a crucial role in solving the pattern formation problem considered in Reference [4], where the solution was used in the first step of the four-step pattern formation algorithm. The benefit was that since the algorithm presented here arranges robots on the corners of a convex hull, we were able to exploit the knowledge of \(N\) obtained after Complete Visibility is solved to plan for how to run steps 2-4 of the pattern formation algorithm of [4]. Several questions remain open. The open questions can be categorized depending on the focus on number of colors, runtime, color/runtime trade-off, and nature of a solution. We discuss open problems in each categories below. Regarding the number of colors, a major open question is to design a 2-color algorithm (ignoring runtime) that works in the asynchronous setting even when robots have non-monotonic movements. Non-monotonic movements meaning that robots may stop before reaching the destination point or change direction before reaching the destination. The existing solutions in this direction provide a 2-color algorithm only in the case of monotonic movements in the asynchronous setting. The same can be done for the case of fat robots and design a color-optimal algorithm. Regarding runtime, a major open question is to design a provably-efficient runtime algorithm in the asynchronous setting with non-monotonic movements. Our result in this paper only provides \(\mathcal{O}(1)\) runtime with monotonic movements. First, of all, it would be interesting to see whether the algorithm of this paper can be extended to establish \(\mathcal{O}(D/\Delta)\) runtime algorithm, where \(D\) is the diameter of the initial configuration and \(\Delta>0\) is the minimum distance a robot travels in each move operation. \(\Delta\) cannot be zero since, otherwise, the problem may not simply be solved. After that, it would be interesting to see whether the \(\mathcal{O}(D/\Delta)\) bound can be improved. Regarding trade-off, a major open question is to minimize the number of colors from current 60 to say 30 (the best possible is 2) without impacting runtime. Can we do better if we could have two lights on a robot so that it can have information on two colors for the two lights than just a single color for the single light? Regarding nature of a solution, a major open question is to solve Complete Visibility without robots needing to be arranged on the corners of a convex hull. Can the runtime of \(\mathcal{O}(1)\) can be achieved for such non-convex hull solution? What about the number of colors? What about handling non-monotonic movements? This aspect can also be considered for fat robots. Furthermore, can the fault-tolerant algorithms be designed for Complete Visibility? There are some algorithms that handle faults in certain cases, but this direction calls for systematic effort to deal with faults under different settings. All the aforementioned aspects can be considered for robots working on a grid setting, as well.