We present BioMASS, a new model to implement a spatially explicit environment that supports constant-time sensory (neighborhood search) and locomotion functions for situated multiagent systems (MAS). In contrast, the spatial models currently provided by agent-based modeling and computer simulation (ABMS) platforms have computational costs that grow quadratically with perception range and linearly with the number of agents. To conserve computation, existing ABMS models of complex systems are oversimplified, by limiting the environment size, perception ranges, or the number of agents. BioMASS achieves constant time search and locomotion for the majority of function calls by implementing a linked list, nearest-neighbor data structure. This model makes the functions largely independent of the environment size, perception range, and the number of agents. We conduct a theoretical and experimental study of BioMASS compared to other spatial models. Experiments performed using a prey-predator swarm model show that BioMASS significantly outperforms the continuous and hybrid models in terms of execution time, allowing for higher-resolution modeling and simulation of complex systems.
A subset S ⊆ V of vertices of an undirected graph G = (V,E) is a hub cover when for each edge (u, v) ∈ E, at least one of its endpoints belongs to S, or there exists a vertex r ∈ S that is a neighbor of both u and v. The problem of computing a minimum hub cover set in arbitrary graphs is NP-hard. This problem has applications for indexing large databases. This paper proposes APX-MHC, the first approximation algorithm for the minimum hub cover set in arbitrary graphs to the best of our knowledge. The approximation ratio of this algorithm is proportional to ln μ, where μ is upper bounded by min{1/2 Δ2, |E|} and Δ is the degree of G. The execution time of APX-MHC is O((Δ + 1)|E| + |S||V|). Experimental results show that APX-MHC far outperforms the theoretical approximation ratio for the input graph instances.
Some probability distributions can be described by relevant parameters, such as the mean and standard deviation for the case of Gaussians. This parameterization defines a manifold in which probability functions can be studied from a geometrical perspective. Information Geometry studies probability functions as points in this parameter-defined space, applying differential geometry. Probability functions can also be described by their mean square error, which can be approximated by a second-degree polynomial. In this contribution, we describe the characterization of probability functions in terms of the coefficients of second-degree polynomials that approximate their mean square error. The parameters of this polynomial define a manifold, approximated by a second-degree polynomial, in which probability distributions from different families can be compared by computing the arc length of the points linked to the distributions. One of the advantages of this approach is that the probability distributions can be compared in a more geometrical perspective. In this contribution, we describe the geometry of the induced manifold, and at the same time, we compare this manifold with the common structures from Information Geometry such as the Fisher–Rao distance. We offer empirical evidence that the characterization of probability distributions based on their mean square error can be of relevance not only for comparing them but also to gain a different look at the relation between probability distributions.