The multi-agent approach has been successfully used for solving more and more complex problems. Recent work carried out in that field has shown the benefits it provides for building decision support applications in a complex realtime environment. We will herein present some work in the field of Command, Control, Communications and Information (C3I) systems, that has been carried out in the context of the $30 million European EUCLID RTP6.1 project. We describe agent-based techniques that have been developed for providing time-critical decision support in a realistic operational context. This has been done by integrating and adapting anytime reasoning techniques to a multi-agent framework. The main objectives of the Cooperative Anytime Agent Model (CAAM) we have proposed were to allow agents to make use of time and computational resources in an optimal manner, and to allow the overall system to take time constraints into account by adapting the accuracy of its results to the time available.