Methods, apparatus, systems, and computer-readable media are provided for using sensor-based observations from multiple agents (e.g., mobile robots and/or fixed sensors) in an environment to estimate the pose of an object in the environment at a target time and to estimate an uncertainty measure for that pose. Various implementations generate a multigraph based on a group of observations from multiple agents, where the multigraph includes a reference frame node, object nodes, and a plurality edges connecting the nodes. In some implementations, a composite pose and composite uncertainty measure are generated for each of a plurality of simple paths along the edges of the multigraph that connect the reference frame node to a given object node—and a pose and uncertainty measure for an object identifier associated with the given object node is generated based on the composite poses and the composite uncertainty measures.