Any recommendations for having randomized obstacles for a nav mesh?

I have a huge maze with monsters following the player and the tunnels are filled with randomized obstacles that only the player should be able to pass (to help him avoid the enemy). The problem is that the obstacles are randomized to give the player a different experience everytime he plays. This will give me problems later on with the AI Navigation. Can you guys help? Thanks in advance

Unity recently added the ability to bake meshes at runtime. So you could spawn your obstacles then bake the mesh afterwards. Just make the objects and player not collide, but the still have them bake to the navmesh so monsters will avoid them.