  Past work on evacuation planning assumes that evacuees will follow
instructions -- however, there is ample evidence that this is not the case.
While some people will follow instructions, others will follow their own
desires. In this paper, we present a formal definition of a behavior-based
evacuation problem (BBEP) in which a human behavior model is taken into account
when planning an evacuation. We show that a specific form of constraints can be
used to express such behaviors. We show that BBEPs can be solved exactly via an
integer program called BB_IP, and inexactly by a much faster algorithm that we
call BB_Evac. We conducted a detailed experimental evaluation of both
algorithms applied to buildings (though in principle the algorithms can be
applied to any graphs) and show that the latter is an order of magnitude faster
than BB_IP while producing results that are almost as good on one real-world
building graph and as well as on several synthetically generated graphs.
