An intelligent agent is a reactive, proactive, autonomous, and social entity. The social ability of an agent is exercised in a multi-agent system (MAS), which constitutes a collection of such agents. Current multi-agent systems mostly work in complex, open, and dynamic environments. In an open environment, many facts, such as domain constraints, agent number, and agent relationships, are not fixed. That brings a lot of difficulties to coordinate agents’ interactions and cooperation. One major problem that impedes agent interaction is that most current agent interaction protocols are not very suitable for open environments. In this chapter, we introduce an approach to ameliorate agent interactions from two perspectives. First, the approach can enable agents to form knowledge “rich” interaction protocols by using ontologies. Second, we use coloured Petri net (CPN) based methods to enable agents to form interaction protocols dynamically, which are more suitable for agent interaction under open environments.