This paper proposes a new method for multi-agent path finding on non-grid maps under conditions of uncertain travel times, with a focus on providing approximate solutions. Prioritized Planning (PP) is a widely acknowledged strategy that plans routes for robots sequentially, taking into account the planned paths of other robots. However, no method based on PP has been applicable under conditions of uncertain travel times. This paper introduces the Stochastic Penalty Path Planning method for single-robot planning to incorporate uncertainties in travel time. By using Monte Carlo simulations to estimate different travel time scenarios and treating collisions as soft constraints with penalties, the new method aims to manage the unpredictable nature of robot movement effectively. We evaluate the proposed method using simulations of real-world warehouse and office scenarios. The experimental results indicate that the proposed method can appropriately consider the interactions between agents and reduce the total travel time compared to baselines.