Harnessing the increasing amount of information available through public and private networks to inform decision making presents a considerable challenge. There is a critical need for a system that integrates and structures diverse information to support user tasks and goals. The system must focus on the relevant information, evaluate trade-offs, and suggest courses of action to the user. Because we cannot ensure that the system can ever capture all information and preferences, planning should be conducted in a mixed-initiative fashion where the user can explore alternatives and override the system suggestions as needed. Heracles II is a constraint-based framework for interactive planning and information gathering. Two contributions of Heracles II address the limitations of previous work. The first is a hierarchically partitioned conditional-constraint-network representation that models the task structure of the application domain. The second is a constraint propagation algorithm that supports flexible user interaction. Heracles II is fully implemented and has been applied to several practical domains such as travel planning and geospatial-information integration.