This paper considers a timed model tailored to study energy savings in transport networks. It focuses on regenerative braking, a situation where the kinetic energy of a vehicle is transformed in electrical energy and sent back in the electrical network. We first describe transport networks, and formalize their semantics as timed runs of an equivalent network of timed automata (NTA). We then consider three problems. The transfer existence problem checks whether a network has the ability to save energy. The ratio maximization problem aims at computing the maximal ratio of energy saved by time unit in the long run, and the threshold problem consists in verifying the existence of a strategy allowing the saving of more energy than a fixed minima. We show that the transfer problem is a reachability question in the region automaton of the NTA, which can be solved in PSPACE. The ratio problem can be solved using Karp’s algorithm on a corner point abstraction for the NTA, yielding an EXPTIME complexity. Finally, the threshold problem requires to address properties of elementary cycles and finite paths of the corner-point automaton, yielding a PSPACE complexity.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Energy Transfer in Timed Cyclic Networks

  • Luca Paparazzo,
  • Loïc Hélouët,
  • Nicolas Markey

摘要

This paper considers a timed model tailored to study energy savings in transport networks. It focuses on regenerative braking, a situation where the kinetic energy of a vehicle is transformed in electrical energy and sent back in the electrical network. We first describe transport networks, and formalize their semantics as timed runs of an equivalent network of timed automata (NTA). We then consider three problems. The transfer existence problem checks whether a network has the ability to save energy. The ratio maximization problem aims at computing the maximal ratio of energy saved by time unit in the long run, and the threshold problem consists in verifying the existence of a strategy allowing the saving of more energy than a fixed minima. We show that the transfer problem is a reachability question in the region automaton of the NTA, which can be solved in PSPACE. The ratio problem can be solved using Karp’s algorithm on a corner point abstraction for the NTA, yielding an EXPTIME complexity. Finally, the threshold problem requires to address properties of elementary cycles and finite paths of the corner-point automaton, yielding a PSPACE complexity.