A communication orchestration service automatically orchestrates dynamic multiple party, multiple media communications. A customer expresses his or her communications needs in the form of a high-level goal or goals. A goal-based search finds a combination of building block predicates that can be used to satisfy the customer's needs. In conjunction with the search process, the mechanism uses the SIP OPTIONS request or presence information to actively query device status and capabilities during the search. This enables the search to actively explore the communications environment at runtime. Once a solution is found, the necessary parties can be contacted, resources can be provisioned, and the multiple media, multiple user collaboration/conference can be initiated.