I haven't tried this before, but give your pathfiding objects the solid behavior, and then once every few ticks regenerate the obstacle map. I'm not positive if each pathfinding object needs to regenerate the map, or if this map is shared by all objects who are pathfinding. If the objects still collide or even clip each other every so often, then experiment with making the cell size and/or cell border bigger.