Humans and robots are becoming co-workers, both in industrial and medical applications. This new paradigm raises problems related to human safety. To accomplish and solve this issue, many researchers have developed collision avoidance strategies—mainly relying on potential field approaches—in which attractive and repulsive virtual forces are generated between manipulators and objects within a collaborative workspace. The magnitude of such virtual forces strongly depends on the relative distance between the manipulators and the approaching agents, as well on their relative velocity. In this paper, authors developed an intrinsically distributed probabilistic algorithm to compute distances between the manipulator surfaces and humans, allowing tuning the computational time versus estimation accuracy, based on the application requirements. At each iteration, the algorithm computes the human–robot distances, considering all the Cartesian points within a specific geometrical domain, built around humans’ kinematic chain, and selecting a random subset of points outside of it. Experimental validation was performed in a dynamic and unstructured condition to assess the performance of the algorithm, simulating up to six humans into the shared workspace. Tests showed that the algorithm, with the selected hardware, is able to estimate the distance between the human and the manipulator with a RMSE of 5.93 mm (maximum error of 34.86 mm).