An agent in a multi-agent system (MAS) has to generate plans for its individual goal, but these plans may conflict with those that are already being scheduled or executed by other agents. It must also be able to complete its planning and resolution of these conflicts within a reasonable time to have an acceptable quality plan. Although we adopt hierarchical planning (HP, for example, see [7, 12]) using the decision-theoretic planning (DTP) approach [6] for efficient planning, it is not trivial to apply HPO to MAS. In HP, appropriate (abstract) plans are selected level by level to maximize the utility U (p), where where p is the expected—nal plan comprising a sequence of primitive actions. However, in the MAS context, conflicts between agents affect the efficiency and quality of resulting plans. When a conflict is found at lower levels, an additional sophisticated process for avoiding it (conflict resolution) must be invoked and some extra actions (such as waiting for synchronization and detouring) may have to be added to the plan. The conflict resolution process may become costly or fail. Even a single conflict, if it is difficult to resolve, will result in a plan with considerably lower quality than it otherwise would have. As a result, in multi-agent systems, the second- or third-best plans may result in better overall performance.