Attribute measurement is an important component of classification algorithms, which could limit their applicability in realtime settings. The time taken to assign a value to an unknown attribute may reduce the overall utility of the final result. We identify three different costs that must be considered, including a time sensitive utility function. We model this attribute measurement problem as a Markov decision process (MDP), and build a policy to control this process using AO* heuristic search. The results offer a cost-effective approach to attribute measurement and classification for a variety of realtime applications.