Several recent research efforts have shown that the bioelectrical stimulation of their neuro-mechanical system can control the locomotion of Madagascar hissing cockroaches (Gromphadorhina portentosa). This has opened the possibility of using these insects to explore centimeter-scale environments, such as rubble piles in urban disaster areas. We present an inertial navigation system based on machine learning modules that is capable of localizing groups of G. portentosa carrying thorax-mounted inertial measurement units. The proposed navigation system uses the agents' encounters with one another as signals of opportunity to increase tracking accuracy. Results are shown for five agents that are operating on a planar (2D) surface in controlled laboratory conditions. Trajectory reconstruction accuracy is improved by 16% when we use encounter information for the agents, and up to 27% when we add a heuristic that corrects speed estimates via a search for an optimal speed-scaling factor.