Redução do espaço de busca de estruturas de coalizão a partir de informações sobre o domínio : uma aplicação em smart grids

Abstract

Redes elétricas desempenham um papel fundamental no que tange à distribuição de energia elétrica. Entretanto, as redes elétricas convencionais são muito antigas, apresentando uma série de deficiências e inseguranças. Neste cenário surgem as redes elétricas inteligentes, mais conhecidas como smart grids. Smart grids são uma evolução para as redes elétricas tradicionais, apresentando como grande diferencial a presença intensiva de tecnologia de ponta para monitorar cada elemento que a compõe. Uma das principais características de smart grids é seu fluxo bidirecional de energia e informação, que permite a qualquer elemento tanto consumir quanto fornecer energia para a rede, seja um aerogerador ou mesmo uma residência. Tal característica vai de encontro à necessidade de se distribuir a produção energética, tornando-a mais robusta e tolerante a falhas. Uma tecnologia que surgiu em meio ao desenvolvimento de smart grids denomina-se Veículo-Para-Rede (V2G, do inglês Vehicle-To-Grid). Através de sessões V2G, veículos elétricos (EVs, em inglês electric vehicles) podem vender a energia de suas baterias para a rede, obtendo lucro com este procedimento. Existem duas vantagens nesta tecnologia. Por um lado, proprietários de EVs podem obter lucro com a venda de energia, reduzindo os custos de se manter seu veículo. Por outro lado, a rede como um todo se beneficia, pois as baterias podem ser utilizadas para aumentar a estabilidade da rede. Entretanto, para que estas vantagens sejam expressivas, é necessário utilizar-se de mecanismos para aumentar a eficiência do processo V2G, uma vez que baterias são muito caras. Uma alternativa que tem sido muito explorada é a formação de coalizões entre os EVs. A proposta deste trabalho é utilizar informações sobre o domínio de smart grids de modo a impor restrições no processo de formação de coalizões de EVs, visando à redução do espaço de busca de estruturas de coalizão. Especificamente, estabelece-se a distância máxima que pode haver entre dois EVs de uma mesma coalizão, através da qual é possível identificar e podar porções inválidas do espaço de busca. Para tanto, é proposto o algoritmo CPCSG, capaz de identificar restrições entre os EVs e de podar o espaço de busca. A abordagem proposta pode ser utilizada em conjunto com algoritmos de geração de estruturas de coalizão para torná-los mais rápidos e eficientes. Com base em experimentos, percebe-se que a abordagem proposta proporciona um ganho notável de desempenho e uma redução expressiva no uso de memória em relação a outros algoritmos para geração de estruturas de coalizão. Em geral, quanto mais restritiva a rede e quanto maior o número de agentes, maior será o percentual do espaço de busca passível de ser podado. Resultados mostram, ainda, que quando comparada com outros algoritmos de geração de estruturas de coalizão, a técnica proposta chega a superar o tempo dos demais em diversas ordens de magnitude.

Electric grids play a key role in the energy distribution process. However, conventional grids are very old, which causes the onset of weaknesses and uncertainties. In such a scenario the smart grid concept arises. Smart grids are an evolution to the ageing electric grids, whose major breakthrough is the intensive use of technology to monitor every element that comprises it. One of the main features of smart grids is its bi-directional flow of electricity and information, which allows any element to consume and even supply energy to the grid, regardless of being a wind turbine or even a residence. Such a characteristic meets the need to make the energy production more distributed, making it more robust and fault tolerant. Amidst the development of smart grids emerged the concept of Vehicle-To-Grid (V2G). Through V2G sessions, electric vehicles (EVs) can sell the surplus energy of their batteries to the grid, making a profit. Two advantages arise from this technology. First, EVs’ owners can make a profit from the sale of energy, reducing their vehicles’ maintenance cost. Second, the network as a whole is benefited as batteries could be used to increase the network stability. However, in order to benefit from such advantages, it is necessary the use mechanisms to increase the efficiency of the V2G process, since batteries are very expensive. One way that has been explored is the coalition formation among EVs. The proposal of this work is to use smart grids’ domain information to impose constraints on the coalition formation process in order to reduce the coalition structures’ search space. Specifically, we define a maximum distance that can exist between two EVs of a given coalition, through which it is possible to identify and prune invalid portions of the search space. To this end, we propose the CPCSG algorithm, which has the capability of identifying constraints among EVs and pruning the search space. The proposed approach can be used together with coalition structure generation algorithms to make them faster and more efficient. Based on experiments, it can be seen that our approach provides a noticeable performance gain and a significant memory usage reduction compared to other coalition structure generation algorithms. In general, the more restrictive the grid and the greater the number of agents, the greater the percentage of the search space that can be pruned. Results also show that when compared with other coalition structure generation algorithms, the proposed technique is able to overcome the other in time by several orders of magnitude.