Author name cluster

Michal Jakob

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

18 papers

2 author rows

ICAPS Conference 2024 Conference Paper

Multi-Objective Electric Vehicle Route and Charging Planning with Contraction Hierarchies

Marek Cuchý
Jirí Vokrínek
Michal Jakob

Electric vehicle (EV) travel planning is a complex task that involves planning the routes and the charging sessions for EVs while optimizing travel duration and cost. We show the applicability of the multi-objective EV travel planning algorithm with practically usable solution times on country-sized road graphs with a large number of charging stations and a realistic EV model. The approach is based on multi-objective A* search enhanced by Contraction hierarchies, optimal dimensionality reduction, and sub-optimal ϵ-relaxation techniques. We performed an extensive empirical evaluation on 182, 000 problem instances showing the impact of various algorithm settings on real-world map of Bavaria and Germany with more than 12, 000 charging stations. The results show the proposed approach is the first one capable of performing such a genuine multi-objective optimization on realistically large country-scale problem instances that can achieve practically usable planning times in order of seconds with only a minor loss of solution quality. The achieved speed-up varies from ~11× for optimal solution to more than 250× for sub-optimal solution compared to vanilla multi-objective A*.

Details

IS Journal 2024 Journal Article

Towards Incremental Development of Human-Agent-Robot Applications using Mixed-Reality Testbeds

Michal Jakob
Michal Pechoucek
Michal Cap
Ondrej Vanek
Peter Novak

Testing is essential part of the development of human-agent-robot team (HART) applications. Individual algorithms in such applications cannot be tested in isolation as their performance depends significantly on complex interactions among distributed software code, humans, hardware and the target environment. Any testing involving robots and human actors is, however, time-consuming and costly. We therefore propose an incremental development framework employing mixed-reality testbeds, which can reduce testing cost by replacing parts of the application and surrounding reality with synthetic computational models. The proposed framework introduces the concept of testbed fidelity and proposes how test reliability and cost should be managed to maximize the effectiveness of the development process. The framework is illustrated on two example applications in the domain of multi-UAV tracking and anti-maritime piracy operations.

Details DOI

AAMAS Conference 2018 Conference Paper

Revenue Maximization for Electric Vehicle Charging Service Providers Using Sequential Dynamic Pricing

Jan Mrkos
Anton�n Komenda
Michal Jakob

With the increasing prevalence of electric vehicles (EVs), the provision of EV charging is becoming a standard commercial service. With this shift, EV charging service providers are looking for ways to make their business more profitable. Dynamic pricing is a proven technique to increase revenue in markets with time-variant, heterogeneous demand. In this paper, we propose a Markov Decision Process (MDP)-based approach to revenue-maximizing dynamic pricing for charging service providers. We implement the approach using an ensemble of policy iteration MDP solvers and evaluate it using a simulation based on real-world data. We show that our proposed method achieves significantly higher revenue than methods utilizing flat-based pricing. In addition to achieving higher revenue for charging service providers, the method also increases the efficiency of allocation measured in terms of the total utilization of the charging station.

PDF

ECAI Conference 2014 Conference Paper

A Profit-Aware Negotiation Mechanism for On-Demand Transport Services

Malcolm Egan
Michal Jakob

As new markets for transportion arise, on-demand transport services are set to grow as more passengers seek affordable personalized journeys. To reduce passenger prices and increase provider revenue, these journeys will often be shared with other passengers. As such, new negotiation mechanisms between passengers and the service provider are required to plan and price journeys. In this paper, we propose a novel profit-aware negotiation mechanism: a multiagent approach that accounts for both passenger and service provider preferences. Our negotiation mechanism prices each passenger's journey, in addition to providing vehicle routing and scheduling. We prove a stability property of our negotiation mechanism using a connection to hedonic games. This connection yields new insights into the link between vehicle routing and passenger pricing. We also show via simulations the dependence of the service provider profit and passenger prices on the number of passengers as well as passenger demographics. In particular, our key observation is that increasing the number of passengers has the effect of increasing passenger diversity, which in turn increases the service provider's profit.

Details

ECAI Conference 2014 Conference Paper

Advanced Public Transport Network Analyser

Jan Nykl
Michal Jakob
Jan Hrncír

We present a web-based tool for a fine-grained analysis of the quality of public transport coverage. Employing an efficient graph-based transport network representation and a fast, modified Dijkstra-based journey planning algorithm, the tool calculates four public transport accessibility indices: journey duration, service frequency, the number of transfers, and a combined, overall index. Together, the indices give an accurate picture of the user-perceived accessibility by public transport in the area and time of interest.

Details

ECAI Conference 2014 Conference Paper

Bicycle Route Planning with Route Choice Preferences

Jan Hrncír
Qing Song 0009
Pavol Zilecky
Marcel Nemet
Michal Jakob

Bicycle route planning is a challenging problem because of the diverse set of factors considered by cyclists in choosing their cycling routes. We provide a solution to this problem based on a formal model expressive enough to represent transport network features and cyclists' preferences grounded in the studies of real-world bicycle route choice behaviour. Our solution employs the A* algorithm together with vectors of cost and heuristic functions - able to optimise routes for travel time, comfort, quietness, and flatness. We have implemented, practically deployed and experimentally evaluated our solution in the challenging setting of the city of Prague. The experiments confirmed that the planner is able to return high-quality plans in less than 250 milliseconds per query.

Details

ECAI Conference 2014 Conference Paper

Personalized Fully Multimodal Journey Planner

Michal Jakob
Jan Hrncír
Luis Oliva
Francesco Ronzano
Pavol Zilecky
Jason Finnegan

We present an advanced journey planner designed to help travellers to take full advantage of the increasingly rich, and consequently more complex offering of mobility services available in modern cities. In contrast to existing systems, our journey planner is capable of planning with the full spectrum of mobility services; combining individual and collective, fixed-schedule as well as on-demand modes of transport, while taking into account individual user preferences and the availability of transport services. Furthermore, the planner is able to personalize journey planning for each individual user by employing a recommendation engine that builds a contextual model of the user from the observation of user's past travel choices. The planner has been deployed in four large European cities and positively evaluated by hundreds of users in field trials.

Details

AAMAS Conference 2012 Conference Paper

AgentPolis: Towards a Platform for Fully Agent-based Modeling of Multi-Modal Transportation

Michal Jakob
Zbynĕk Moler
Anton
iacute; n Komenda
Zhengyu Yin
Albert Xin Jiang
Matthew Johnson
Michal Pĕchouček

\textsc{AgentPolis} is a fully agent-based platform for modeling multi-modal transportation systems. It comprises a high-performance discrete-event simulation core, a cohesive set of high-level abstractions for building extensible agent-based models and a library of predefined components frequently used in transportation and mobility models. Together with a suite of supporting tools, \textsc{AgentPolis} enables rapid prototyping and execution of data-driven simulations of a wide range of mobility and transportation phenomena. We illustrate the capabilities of the platform on a model of fare inspection in public transportation networks.

PDF

AAMAS Conference 2012 Conference Paper

Agents vs. Pirates: Multi-agent Simulation and Optimization to Fight Maritime Piracy

Michal Jakob
Ondřej Vanĕk
Ondřej Hrstka
Michal Pĕchouček

Contemporary maritime piracy presents a significant threat to the global shipping industry, with annual costs estimated at up to US\$12bn. To address the threat, commanders and policymakers need new data-driven decision-support tools that will allow them to plan and execute counter-piracy activities most effectively. So far, however, the provision of such tools has been very limited. To fill this gap, we have employed the multi-agent approach and developed a novel suite of computational tools and techniques for operational management of counter-piracy operations. A comprehensive agent-based simulation enables the stakeholders to assess the efficiency of a range of piracy counter-measures, including recommended transit corridors, escorted convoys, group transit schemes, route randomization and navy patrol deployments. Decision-theoretic and game-theoretic optimization techniques further assist in discovering counter-measure configurations that yield the best trade-off between transportation security and cost. We demonstrate our approach on two case studies based on the problems and solutions currently explored by the maritime security community. Our work is the first integrated application of agent-based techniques to high-seas maritime security and opens a wide range of directions for follow-up research and development.

PDF

AAMAS Conference 2011 Conference Paper

, a prototype system that demonstrates how agent-based traffic management techniques can be used to improve the security of transit through piracy-affected areas. Combining agent-based modeling and simulation of maritime traffic and novel route planning and vessel scheduling techniques, the system shows the promising potential of agent-based methods for increasing maritime security. AgentC: Agent-based System for Securing Maritime Transit

Michal Jakob
#X159; ej Van
#X11b; k
Branislav Bo
#X161; ansk
yacute;
Ond
#X159; ej Hrstka

Recent rise in maritime piracy prompts the search for novel techniques for addressing the problem. We therefore developed AgentC

PDF

AAMAS Conference 2011 Conference Paper

Computing Time-Dependent Policies for Patrolling Games with Mobile Targets

Branislav Bo
#X161; ansk
Viliam Lis
yacute;
Michal Jakob
Michal P
#X11b; chou
#X10d; ek

We study how a mobile defender should patrol an area to protect multiple valuable targets from being attacked by an attacker. In contrast to existing approaches, which assume stationary targets, we allow the targets to move through the area according to an a priori known, deterministic movement schedules. We represent the patrol area by a graph of arbitrary topology and do not put any restrictions on the movement schedules. We assume the attacker can observe the defender and has full knowledge of the strategy the defender employs. We construct a game-theoretic formulation and seek defender's optimal randomized strategy in a Stackelberg equilibrium of the game. We formulate the computation of the strategy as a mathematical program whose solution corresponds to an optimal time-dependent Markov policy for the defender. We also consider a simplified formulation allowing only stationary defender's policies which are generally less effective but are computationally significantly cheaper to obtain. We provide experimental evaluation examining this trade-off on a set of test problems covering various topologies of the patrol area and various movement schedules of the targets.

PDF

AAMAS Conference 2011 Conference Paper

Iterative Game-theoretic Route Selection for Hostile Area Transit and Patrolling

Ond
#X159; ej Van
#X11b; k
Michal Jakob
Viliam Lis
Branislav Bo
#X161; ansk
yacute;

A number of real-world security scenarios can be cast as a problem of transiting an area patrolled by a mobile adversary, where the transiting agent aims to choose its route so as to minimize the probability of encountering the patrolling agent, and vice versa. We model this problem as a twoplayer zero-sum game on a graph, termed the transit game. In contrast to the existing models of area transit, where one of the players is stationary, we assume both players are mobile. We also explicitly model the limited endurance of the patroller and the notion of a base to which the patroller has to repeatedly return. Noting the prohibitive size of the strategy spaces of both players, we employ iterative oracle-based algorithms including a newly proposed accelerated scheme, to obtain optimum route selection strategies for both players. We evaluate the developed approach on a range of transit game instances inspired by real-world security problems in the urban and naval security domains.

PDF

IS Journal 2011 Journal Article

Using Agents to Improve International Maritime Transport Security

Michal Jakob
Ondrej Vanek
Michal Pechoucek

Agent-based techniques have the potential to improve the security of international maritime transport threatened by a steep rise of maritime piracy. We have demonstrated that a randomized route-selection strategy resulting from a normal two-player game formulation of the transit problem can decrease the number of attacks and the payoff accumulated by pirates. Coordinating the movement of patrol and transit vessels without a central authority requires techniques for semi-cooperative planning and coalition formation. With regard to existing applications of agent-based techniques, the maritime domain seems currently under-represented compared to other traffic and transportation domains. This work is a first step in addressing the situation and bringing this important domain into the focus of researchers in the multiagent systems field.

Details DOI

AAMAS Conference 2010 Conference Paper

AgentC: Agent-based Testbed for Adversarial Modeling and Reasoning in the Maritime Domain

Michal Jakob
Ondŕej Vanék
Štép
aacute; n Urban
Petr Benda
Michal Péchouček

We present an agent-based system for modeling, analyzingand reasoning in the maritime domain with the emphasis ondetecting, anticipating and preventing illegal activities, suchas contemporary maritime piracy. At the core of the systemis a data-driven agent-based simulation which combines arange of sources of crime-related real-world data with simulated operation of thousands of vessels of different typesin order to create a rich model of maritime activity. Thesimulation is integrated with a number of advanced reasoning methods for analyzing illegal activities and for planningactive counter-measures. In combination with experimentsupport tools and a powerful user frontend based on GoogleEarth, the testbed provides a complete environment for thedevelopment and evaluation of anti-maritime-crime methodsbased on the multi-agent approach.

PDF

AAMAS Conference 2010 Conference Paper

Occlusion-aware Multi-UAV Surveillance

Eduard Semsch
Michal Jakob
Dusan Pavlicek
Michal Péchouček

We present an agent-based coordination and planning methodfor autonomous aerial surveillance of multiple urban areasusing a group of fixed-wing unmanned aerial vehicles (UAVs). The goal of the surveillance is to observe a set of groundpoints of interest within the target areas as often as possible. The method differs from the existing work by explicitconsideration of sensor occlusions that can occur due to highbuildings and/or other obstacles in the target area. The solution employs a decomposition of the problem in two subproblems: the problem of single-area surveillance and theproblem of allocating UAVs to multiple areas. The overallmethod is evaluated empirically on a realistic simulation ofaerial surveillance built using the AgentFly framework.

PDF

AAMAS Conference 2009 Conference Paper

Adversarial Search with Procedural Knowledge Heuristic

Viliam Lisý
Branislav Bošanský
Michal Jakob
Michal Pĕchouček

We introduce an adversarial planning algorithm based on game tree search, which is applicable in large-scale multiplayer domains. In order to tackle the scalability issues of game tree search, the algorithm utilizes procedural knowledge capturing how individual players tend to achieve their goals in the domain; the information is used to limit the search only to the part of the game tree that is consistent with pursuing players’ goals. We impose no speciﬁc requirements on the format of the procedural knowledge; any programming language or agent speciﬁcation paradigm can be employed. We evaluate the algorithm both theoretically and empirically, conﬁrming that the proposed approach can lead to a substantial search reduction with only a minor negative impact on the quality of produced solutions.

PDF

ICAART Conference 2009 Conference Paper

Goal-based Adversarial Search - Searching Game Trees in Complex Domains using Goal-based Heuristic

Viliam Lisý
Branislav Bosanský
Michal Jakob
Michal Pechoucek

We present a novel approach to reducing adversarial search space by using background knowledge represented in the form of higher-level goals that players tend to pursue in the game. The algorithm is derived from a simultaneous-move modification of the maxn algorithm by only searching the branches of the game tree that are consistent with pursuing player’s goals. The algorithm has been tested on a real-world-based scenario modelled as a large-scale asymmetric game. The experimental results obtained indicate the ability of the goalbased heuristic to reduce the search space to a manageable level even in complex domains while maintaining the high quality of resulting strategies.

Details

AAMAS Conference 2008 Conference Paper

Case Studies for Contract-based Systems

Michal Jakob
Michal P? chou? ek
Simon Miles
Michael Luck

Of the ways in which agent behaviour can be regulated in a multiagent system, electronic contracting – based on explicit representation of different parties' responsibilities, and the agreement of all parties to them – has significant potential for modern industrial applications. Based on this assumption, the CONTRACT project aims to develop and apply electronic contracting and contract-based monitoring and verification techniques in real world applications. This paper presents results from the initial phase of the project, which focused on requirements solicitation and analysis. Specifically, we survey four use cases from diverse industrial applications, examine how they can benefit from an agent-based electronic contracting infrastructure and outline the technical requirements that would be placed on such an infrastructure. We present the designed CONTRACT architecture and describe how it may fulfil these requirements. In addition to motivating our work on the contractbased infrastructure, the paper aims to provide a much needed community resource in terms of use case themselves and to provide a clear commercial context for the development of work on contract-based system.

PDF