Tenda Okimoto

Automated collision avoidance is a central topic in multi-agent systems that consist of mobile agents. One simple approach to pursue system-wide performance is a centralized algorithm, which, however, becomes computationally expensive when involving a large number of agents. There have thus been proposed fully distributed collision avoidance algorithms that can naturally handle many-to-many encounter situations. The DSSA⁺ is one of those algorithms, which is heuristic and incomplete but has lower communication and computation overheads than other counterparts. However, the DSSA⁺ and some other distributed collision avoidance algorithms basically optimize the agents’ behavior only in the short term, not caring about the total efficiency in their paths. This may result in some agents’ paths with over-deviation or over-stagnation. In this paper, we present Distributed Stochastic Search algorithm with a deep Q-network (DSSQ), in which the agents can generate time-efficient collision-free paths while they learn independently whether to detour or change speeds by Deep Reinforcement Learning. A key idea in the learning principle of the DSSQ is to let the agents pursue their individual optimality. We have experimentally confirmed that a sequence of short-term system-optimal solutions found by the DSSA⁺ gradually becomes long-term individually optimal for every agent.

The increasing complexity of maritime traffic imposes growing demands on the safety and rationality of ship-collision-avoidance decisions. While most existing research focuses on simple encounter scenarios, autonomous collision-avoidance strategies that comply with the International Regulations for Preventing Collisions at Sea (COLREGs) in complex multi-ship environments remain insufficiently investigated. To address this gap, this study proposes a novel collision-avoidance framework that integrates a quantitative COLREGs analysis with a distributed stochastic search mechanism. The framework consists of three core components: encounter identification, safety assessment, and stage classification. A cost function is employed to balance safety, COLREGs compliance, and navigational efficiency, incorporating a distance-based weighting factor to modulate the influence of each target vessel. The use of a distributed stochastic search algorithm enables decentralized decision-making through localized information sharing and probabilistic updates. Extensive simulations conducted across a variety of scenarios demonstrate that the proposed method can rapidly generate effective collision-avoidance strategies that fully comply with COLREGs. Comprehensive evaluations in terms of safety, navigational efficiency, COLREGs adherence, and real-time computational performance further validate the method’s strong adaptability and its promising potential for practical application in complex multi-ship environments.

The proper operation of security guards is one of the major issues in public institutions. By assigning the security guard to the most appropriate duty areas and time-slots, the service can be provided in the best conceivable way. Security Guard Scheduling Problem (SGSP) is a combinatorial optimization problem, in which a set of security guards must be assigned into a limited set of working slots, subject to a given set of constraints. In the real world, it is natural to consider the scheduled security guard’s unexpected absences, e.g., illness, accident and injury of a security guard. In addition, it is required to respond immediately to the unexpected additional security works in case of emergency. Robustness, i.e., the ability to satisfy the security level even if some security guards break down, and the ability to respond immediately to the unexpected additional security works, is an expected property of a security guard team. In this paper, the main focus is laid on the Robust Security Guard Scheduling Problem (R-SGSP) . Two formal frameworks are defined, namely Proactive Security Guard Scheduling Problem with Robustness (R-SGSPpro) and Reactive Security Guard Scheduling Problem with Robustness (R-SGSPre), and some decision and optimization problems for R-SGSPpro and R-SGSPre are provided. Furthermore, zero-one integer programming formulations for the R-SGSPpro and R-SGSPre are provided. Finally, some empirical results for R-SGSPpro and R-SGSPre are reported.

Sports scheduling is one of the widely investigated application problems in artificial intelligence and operations research. This problem can be represented as a combinatorial optimization problem, in which the date and the venue of each game must be determined, subject to a given set of constraints. In 2018, Japan Basketball Association (JBA) has started to implement the league games in the prefectures, and regarding U12 (under 12 years old), league games are currently being held in most prefectures. In this paper, the main focus is laid on the U12 Basketball League Scheduling Problem. First, a formal framework for the U12 Basketball League Scheduling based on minimizing the total traveling distance (U12-BLSdist) is defined. A novel solution criterion called an egalitarian solution for U12-BLSdist is also provided. Next, a formal framework for the U12 Basketball league scheduling problem based on minimizing the number of breaks (U12-BLSbreak) is defined. Furthermore, the frameworks U12-BLSdist and U12-BLSbreak are formalized as 0-1 integer programming problems. In the experiments, we use the real data of U12 basketball league games played in Hyogo prefecture in 2018 and solve the U12-BLSdist and U12-BLSbreak problems. An optimal league scheduling and an egalitarian league scheduling for the U12-BLSdist, and the minimal number of breaks for the U12-BLSbreak are reported by comparing with the league scheduling actually used in 2018.

To the best of our knowledge, there have been very few work on computational algorithms for the core or its variants in MC-nets games. One exception is the work by [Hirayama, et.al., 2014], where a constraint generation algorithm has been proposed to compute a payoff vector belonging to the least core. In this paper, we generalize this algorithm into the one for finding a payoff vector belonging to ϵ-core with pre-specified bound guarantee. The underlying idea behind this algorithm is basically the same as the previous one, but one key contribution is to give a clearer view on the pricing problem leading to the development of our new general algorithm. We showed that this new algorithm was correct and never be trapped in an infinite loop. Furthermore, we empirically demonstrated that this algorithm really presented a trade-off between solution quality and computational costs on some benchmark instances.

Distributed Constraint Optimization Problem (DCOP) has been studied as a fundamental component of multiagent systems. With DCOPs, various applications on multiagent systems are formalized as constraint optimization problems where variables and functi