Best-of-n problems have been rigorously studied in the context of swarm intelligence. However, most solutions to this problem rely on a series of assumptions such as prior knowledge about the number or features of available options. In this study, we investigate a collective perception task with no prior knowledge about option features, in a dynamic environment. The added constraint renders previous approaches impractical, as robots are no longer able to use option features to identify them when communicating. To resolve this problem, we propose a novel probabilistic Naming Game routine that allows agents to converge on words that uniquely identify such features. We also propose a new quality estimation method that is compatible with the proposed Naming Game routine and easier to optimise. We compare the proposed approach with two baselines: decision convergence without communication, and decision convergence with pre-existing identifiers. We perform scalability tests for larger swarm sizes in larger environments. Our findings indicate that swarms utilising the probabilistic Naming Game to interpret neighbours’ communication signals for the purpose of quality estimation generally performed better than swarms that do not communicate and that this behaviour is relatively scalable. We also found that swarms using communication suffer from social inertia, that impacts the probabilistic Naming Game swarms less than swarms with prior environmental information.