Ambient Intelligence (AmI) is a user-centric paradigm offering self-adaptive environments and tailor-made services. A fundamental component of an AmI environment is a service allocation system. In this paper, we present a mathematical model for service allocation in a multiagent-based AmI environment that exhibits heterogeneous resources and energy constraints. We also propose a heuristic, probabilistic search algorithm for efficiently solving the provisioning problem. Results show that our model achieves optimal service allocations that trade-off the number of services offered by the agents and their energy consumption, thereby reducing the overall response time of the AmI environment and its energy use. (C) 2017 Elsevier B.V. All rights reserved.