High communication efforts and poor problem solving results due to restricted overview are two central issues in collaborative problem solving. This work addresses these issues by introducing the processes of agent melting and agent splitting that enable individual problem solving agents to continually and autonomously reconfigure and adapt themselves to the particular problem to be solved. The author provides a sound theoretical foundation of collaborative problem solving itself and introduces various new design concepts and techniques to improve its quality and efficiency, such as the multi-phase agreement finding protocol for external problem solving, the composable belief-desire-intention agent architecture, and the distribution-aware constraint specification architecture for internal problem solving.The practical relevance and applicability of the concepts and techniques provided are demonstrated by using medical appointment scheduling as a case study.