In Agent Based Scheduling and Planning Systems, autonomous agents are used to represent enterprises and operating scheduling/planning tasks. As application domains become more and more complex, agents are required to handle a number of changing and uncertain factors. This requirement makes it necessary to embed state prediction mechanisms in Agent Based Scheduling and Planning Systems. In this chapter, we introduce a Colored Petri Net based approach that use Colored Petri Net models to represent relative dynamic factors of scheduling/planning. Furthermore, in our approach, we first introduce and adopt an improved Colored Petri Net model which can not only analyse future states of a system but also estimate the success possibility of reaching a particular future state. By using the improved Colored Petri Net model, agents can predict the possible future states of a system and risks of reaching those states. Through embedding such mechanisms, agents can make more rational and accurate decisions in complex scheduling and planning problems. © 2009 Springer-Verlag Berlin Heidelberg.