# ORTAC+: A User Friendly Domain Specific Language for Multi-Agent Mission Planning

Caroline Bonhomme, Jean-Louis Dufour

► To cite this version:

Caroline Bonhomme, Jean-Louis Dufour. ORTAC+: A User Friendly Domain Specific Language for Multi-Agent Mission Planning. ECAI Third Workshop on Agents and Robots for reliable Engineered Autonomy 2023 (AREA'23), Oct 2023, Cracovie, Poland. pp.127 - 133, 10.4204/eptcs.391.14. hal-04628845

HAL Id: hal-04628845

https://hal.science/hal-04628845v1

Submitted on 28 Jun 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# ORTAC+: A User Friendly Domain Specific Language for Multi-Agent Mission Planning

Caroline Bonhomme

Safran Electronics and Defense
Massy, France

ONERA
Toulouse, France

caroline.bonhomme@safrangroup.com

Jean-Louis Dufour

Safran Electronics and Defense
Massy, France

jean-louis.dufour@safrangroup.com

A tactical military unit is a complex system composed of many agents such as infantry, robots, or drones. Given a mission, an automated planner can find an optimal plan. Therefore, the mission itself must be modeled. The problem is that languages like PDDL are too low-level to be usable by the end-user: an officer in the field. We present ORTAC+, a language and a planning tool designed for this end-user. Its main objective is to allow a natural modeling of the mission, to minimize the risk of bad modeling, and thus obtain reliable plans. The language offers high-level constructs specifically designed to describe tactical missions, but at the same time has clear semantics allowing a translation to PDDL, to take advantage of state-of-the-art planners.

## 1 Introduction

A tactical military ground unit is a complex system composed of many agents, such as infantry sections, armored units, ground robots, or flying drones. A typical mission lasts one day and is a mix of displacements on a road network of 20 km between given start and finish points and actions. We deal only with the reconnaissance action of a route or an area when an enemy presence is suspected. For us, the reconnaissance action is equivalent to a speed reduction of the progression on a route and exploration of an area. The progression and exploration should be done more safely, thus it is slower. It could be seen as the first visit to a location. This brings us to a variant of the classic Multi-Agent Path Finding (MAPF) problem [1]. Of course, if we consider moves as actions, this is also a multi-agent planning problem [2], but classification as a MAPF problem is more accurate.

Given a mission, if it is described in a programming language, an automated planner can find an optimal plan. Therefore the mission itself must be modeled. The automated planning community has developed the PDDL language in order to specify high level planning problems [3]. However, the specification of the mission should be done by an officer in the field who is not an expert in automated planning. Languages like PDDL are too low-level to be usable by the defined end-user who is not an expert in planning. This is why we present ORTAC+. Its main objective is to allow a natural modeling of the mission, so as to minimize the risk of errors on the modeling of the desired mission, and thus obtain reliable plans. The language is composed by high-level constructs specifically designed to facilitate the specification of tactical missions, with a clear semantic allowing a translation to PDDL, to take advantage of state-of-the-art planners. Planning is done offline, and the plans are deterministic, with no contingency. The default assumption is that the enemy, when suspected, is in fact not present. Otherwise, if there is contact with the enemy, the execution of the plan is de facto interrupted in the field, and the officer must replan with modified objectives.

We proceed by presenting related work of the paper in section 2. The domain-specific language ORTAC+ is presented in section 3, the operational context in section 4, and the conclusion in section 5.

A. Ferrando, R.C. Cardoso (Eds.): Third Workshop on Agents and Robots for reliable Engineered Autonomy 2023 (AREA'23) EPTCS 391, 2023, pp. 127-133, doi:10.4204/EPTCS.391.14

© C. Bonhomme, J-L. Dufour
This work is licensed under the
Creative Commons Attribution License.
## 2 Related Work

ORTAC stands for "Optimal Resource and Technical Action Control". It is a multi-agent planning language and tool combining constraint-solving techniques with advanced search strategy to deconflict single-agent plans [4]. At the language level, ORTAC is innovative in the constraints of coordination between units introducing the notion of "support" explained later [4]. The proper term for that is "cross-schedule dependencies" [5], typically in the case of "coalition formation."

PDDL is the standard planning language used commonly by the automated planning community. One of the purposes of PDDL was to benchmark planning algorithms. Since its creation in 1998 for the International Planning Competition [6], the language evolved to model more complex planning problems as temporal or numerical planning [3]. The Competition of Distributed and Multiagent Planners [7] benchmarks some centralized and decentralized algorithms with an extension of PDDL for multiagent planning as a reference language. ORTAC and PDDL are powerful tools for modeling high-level missions and finding a corresponding plan, nevertheless, they cannot be used by an end-user.

In recent years, an effort on designing domain specific languages (DSL) for non-expert in robotics raised in the research community. Indeed, some of these languages lack clear semantics [8]. Additionnaly, users are required to define the behavior of each robot. Consequently, the autonomy of the system is hindered. Theses systems lack planning capabilities, making it challenging to initiate the integration of planning tools. The research community uses PDDL as the standard task planing language. However, its integration into robotics remains limited. To remedy this issue, efforts were done to integrate planning in robotics [9].

## 3 ORTAC+

ORTAC+ is a tool that assists a military officer in planning a mission. It is a language that aims to be expressive with well-defined syntax and semantics. To do that, the language should allow the description of a given mission and be compatible with automated planners. A military mission is limited in space and time. The first version of ORTAC+ emphasizes the spatial aspects of the mission. The temporal aspects will be added in future works.

### 3.1 Problem Definition

The missions could be seen as a multi-agent planning problem where each agent collaborates to reach a global goal. However, we only consider agents movements. Thus, the model is a variant of a MAPF problem. A classical MAPF problem is represented with a set of agents with an initial position and a target position, in an undirected graph. The solution of a classical MAPF problem is a set of single-agent paths that does not collide [1]. ORTAC+ allows the description of this kind of problem but aims to be more general with the following variants:

* Targets are no longer assigned to each agent but to teams of agents, leading to the possibility of having less target positions than agents. Several agents could be assigned to the same target position but only one of them should reach it.

* Spatial constraints are added to the problem. The constraint can be forbidden or enforced vertex for specific agent.

* Agents can be heterogeneous. While classical MAPF problems harnesses agents with similar characteristics, our problem differs in this aspect.

* The position of an agent is not only on vertices but can be on edges too. The path of an agent is then a succession of vertices and edges.
<table><caption>Table 1: Existing predicates in ORTAC+ DSL. Other predicates can be constructed</caption><thead><tr><td>Predicates</td><td>Description</td><td>Logic formula</td></tr></thead><tbody><tr><td>node_goal(node, agent)</td><td>The location of agent should be node at the final state</td><td>agent.loc(t<sub>final</sub>) = node</td></tr><tr><td>node_visit(node, agent)</td><td>Agent should visit node during execution</td><td>∃t ∈ [[t<sub>initial</sub>; t<sub>final</sub>]],<br/>agent.loc(t) = node</td></tr><tr><td>edge_visit.edge, agent)</td><td>Agent should visit edge during execution</td><td>∃t ∈ [[t<sub>initial</sub>; t<sub>final</sub>]],<br/>agent.loc(t) = edge</td></tr><tr><td>node_avoid(node, agent)</td><td>Agent should never visit node</td><td>∀t ∈ [[t<sub>initial</sub>; t<sub>final</sub>]],<br/>agent.loc(t) ≠ node</td></tr><tr><td>edge_avoid.edge, agent)</td><td>Agent should never visit edge</td><td>∀t ∈ [[t<sub>initial</sub>; t<sub>final</sub>]],<br/>agent.loc(t) ≠ edge</td></tr><tr><td>node_supported_from(node<sub>1</sub>,<br/>node<sub>2</sub>)</td><td>An agent can visit node<sub>1</sub> only if another agent supports him in node<sub>2</sub></td><td>∀t ∈ [[t<sub>initial</sub>; t<sub>final</sub>]], ∀agent,<br/>agent.loc(t) = node<sub>1</sub> ⇒<br/>∃agent<sub>2</sub> ≠ agent,<br/>agent<sub>2</sub>.loc(t) = node<sub>2</sub></td></tr></tbody></table>

predicate([o1,o2], list2, ...) ⇔ predicate(o1, list2, ...) & predicate(o2, list2, ...)

Because of the multi-agent nature of the model, coordination constraints could be required. We are interested in the coordination presented in ORTAC [4]. The main coordination predicate uses quantitative time, but if we restrict ourselves to causality, it boils down to: support(unit1, node1, unit2, node2) which means: "when unit1 goes through node1 (if it goes there), unit2 must be in node2". For this to make sense, node1 and node2 must be close enough, and from a tactical point of view, it is the standard way to progress in dangerous areas. However, we are no longer specifying the mission, but have begun designing the plan. We will call ORTAC's description style "imperative", and ORTAC+ will add a new style that we will call "declarative": node_supported_from(node1, node2) which means: "when an agent goes through node1, another agent must be in node2". This first addition to ORTAC will be called "anonymization", it is not a generic evolution because it is only suitable for certain predicates like support or goal. And concerning goals, their "anonymization" corresponds to an interesting variant of MAPF initially called "permutation-invariant" [10] and today called "anonymous" [11].

### 3.2.3 Ontology

Considering the specificity of our language for its domain, the proposal entails adding a knowledge base to augment its capability. This knowledge base is an ontology designed to help the mission specification. The characteristics of the agents is defined with the declarative predicate presented in the section 3.2.1.

It is possible to specify a constraint involving several agents. For example, considering a mission with two types of agents, an agent can be a "UAV" for unmanned aerial vehicle or a "UGV" for unmanned ground vehicle. This characteristics will be define as an attribute of the agents. Instead of writing: `node_goal(14, [agent1, agent2])`, it is possible to write `node_goal(14, "UGV")` if agent1 and agent2 have the attribute UGV, meaning at the end of the mission a "UGV" should be at the node 14.

Another example of the combined efficiency of objects and ontologies is: french infantry uses impressive vehicles called "VBCI" which need some place to maneuver. If the officer wants to ban the progression of these vehicles on narrow roads, he has to stipulate: `edge_avoid("width < 10", "VBCI")` in spite of `edge_avoid(list_of_edges_with_width Less than 10, list_of_units_with_VBCI)`

Currently, the ontology is hierarchical. An attribute can be a leaf in knowledge tree. For instance, if
agent1 is a UGV on wheels and agent2 is a UGV on caterpillars. There are the relations: a UGV with wheels is a UGV, and the UGV on caterpillars is a UGV. They have the same parent. The ontology allows to specify *node goal(14, "UGV")* to involve agent1 and agent2 in the constraint.

# 4 Operational Context

ORTAC+ is built to specify military missions in order to assist an officer planning the mission. In the following part, an example of mission is described, then its representation in the proposed language.

## 4.1 Description of the Mission

<figure><img src="image_2.png" /><figcaption>Figure 1: Cartography of the mission in Goma, Congo.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Figure 2: Geographical mission modelisation using graphs</figcaption></figure>

Congolese rebels, supported by elements from Rwanda, are located in the eastern region of Goma. The rebels raise a significant threat to the peace and security of the city. The mission focused on two specific objectives: securing the United Nation (UN) point at the border, between Congo and Rwanda, and preparing for the potential evacuation of civilians at the airport. With forces comprising 4 distinct military sections and 4 motorized companies positioned along the west cost of the city, this mission implies the recognition of crucial points and axes leading to the destination goals.

**Operational constraint.** Units follow specific rules of engagements during the execution of their tasks:

* Simultaneous coexistence of two distinct units at the same spatial coordinates is not allowed.

* Any unit advancing on a main street or an intersection must be supported by another unit recently deployed to an adjacent position.

**Tactical information.** The mission encompasses critical data as a foundation for modeling and planning:

* The airport: the airport is a crucial point and must be controlled during the mission, with a designated convoy of one company and one unit equipped with night vision glasses will be tasked to evacuate people from the airport.

* Securing the UN point: The UN point is identified at the border, requiring strict security measures, with a priority to maintain control over

* Support team: A support team will be positioned at the southern region of the operation area
<figure><img src="image_4.png" /><figcaption>Figure 3: Specification of the "Secure the UN in Goma" mission in ORTAC+</figcaption></figure>

## 4.2 Mission specification in ORTAC+

An example of the mission specification in ORTAC+ is given in Figure 3. The mission goal is the securing of the United Nations. The cartography of the mission is given in Figure 1. Friendly forces are blue rectangles at the west of Goma. Target positions are triangles at the east near to enemies in red rectangles. The black triangle correspond to the airport and the red one the UN. The 3 axis of representation (geography, resources and operations) appear clearly combined with the construction of a hierarchical ontology. Geography elements of the mission are supposed to be already given. It is represented in Figure 2 The Goma mission involves two types of agents: compagnies and sections. The predicates `agent_definition()` is used to instantiate the units. At the initial state, the 4 mechanized compagnies are at the same node (9). This violates the constraint that only one unit can be at a node at the same time. That's why the notion of capacity is introduced for nodes and edges. By default the capacity of a node or an edge will be 1 but it can be changed for some exceptions. The method `attribute()` allows the user to add some characteristics to the units. Then, the high level predicates described earlier are used to add the constraints of the mission. The final state is defined with the predicate `node_goal()` with the help of the knowledge base. A compagny should be at the node 11, corresponding to the airport, at the final state. Other constraints are defined, for instance, the unit1 should visit the node 9 but avoid the edge (9,8). ORTAC+ introduces coordination constraints. If an enemy is suspected on a node or an edge, a unit cannot visit it without support. Therefore, the predicate `node_supported_from()` model this coordination. In the presented example, it is specified in order to visit the node 3, there must be a support at the node 18.

# 5 Conclusion

We have presented ORTAC+, a DSL that hopefully permits a military officer to specify a mission. Compared to its predecessor, ORTAC, the evolution can be summarized as follows:

1. predicates are anonymized when suitable, in particular for the declaration of goals or supports and operate on lists of homogeneous objects (agents, nodes, or edges),

2. these lists can be described intentionally, with a propositional sub-language constraining the attributes of objects,

3. these propositions, when they involve the `or` operator, can be shortened thanks to the declaration of the adequate ontology.

As a result, ORTAC+ allows more compact and declarative models, which will be more easily written and checked by end-users. At the same time, we take care to keep semantics to allow a translation to PDDL, making it possible to rely on the existing planners. Current and future work explores 3 orthogonal directions: new coordination constraints, quantitative time and resources, and compatibility with flying drones.
References

[1] Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, TK Kumar, et al. Multi-agent pathfinding: Definitions, variants, and benchmarks. In *Proceedings of the International Symposium on Combinatorial Search*, volume 10, pages 151–158, 2019. doi:10.48550/arXiv.1906.08291.

[2] Alejandro Torreño, Eva Onaindia, Antonín Komenda, and Michal Štolba. Cooperative multi-agent planning: A survey. *ACM Comput. Surv.*, 50(6), 2017. doi:10.1145/3128584.

[3] Patrik Haslum, Nir Lipovetzky, Daniele Magazzeni, Christian Muise, Ronald Brachman, Francesca Rossi, and Peter Stone. *An introduction to the planning domain definition language*, volume 13. Springer, 2019. doi:10.1007/978-3-031-01584-7.

[4] Christophe Guettier, Willy Lamal, Israel Mayk, and Jacques Yelloz. Design and experiment of a collaborative planning service for netcentric international brigade command. In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 29, pages 3967–3974, 2015. doi:10.1609/aaai.v29i2.19055.

[5] G Ayorkor Korsah, Anthony Stentz, and M Bernardine Dias. A comprehensive taxonomy for multi-robot task allocation. *The International Journal of Robotics Research*, 32(12):1495–1512, 2013. doi:10.1177/0278364913496484.

[6] Derek Long, Henry Kautz, Bart Selman, Blai Bonet, Hector Geffner, Jana Koehler, Michael Brenner, Joerg Hoffmann, Frank Rittinger, Corin R. Anderson, Daniel S. Weld, David E. Smith, Maria Fox, and Derek Long. The aips-98 planning competition. *AI Magazine*, 21(2):13, 2000. doi:10.1609/aimag.v21i2.1505.

[7] Michal Stolba, Antonin Komenda, and Daniel Kovacs. Competition of distributed and multiagent planners (codmap). In *Proceedings of the AAAI Conference on Artificial Intelligence*, volume 30, 2016. doi:10.1609/aaai.v30i1.9870.

[8] Swaib Dragule, Thorsten Berger, Claudio Menghi, and Patrizio Pelliccione. A survey on the design space of end-user-oriented languages for specifying robotic missions. *Software and Systems Modeling*, 20(4):1123–1158, February 2021. doi:10.1007/s10270-020-00854-x.

[9] Erez Karpas and Daniele Magazzeni. Automated planning for robotics. *Annual Review of Control, Robotics, and Autonomous Systems*, 3:417–439, 2020. doi:10.1146/annurev-control-082619-100135.

[10] S. Kloder and S. Hutchinson. Path planning for permutation-invariant multirobot formations. *IEEE Transactions on Robotics*, 22(4):650–665, August 2006. doi:10.1109/tro.2006.878952.

[11] Hang Ma and Sven Koenig. Optimal target assignment and path finding for teams of agents. *arXiv preprint arXiv:1612.05693*, 2016. doi:10.48550/arXiv.1612.05693.

[12] Jingjin Yu and Steven M. LaValle. Multi-agent path planning and network flow. In *Springer Tracts in Advanced Robotics*, pages 157–173. Springer Berlin Heidelberg, 2013. doi:10.1007/978-3-642-36279-8_10.

[13] Bernhard Nebel. On the computational complexity of multi-agent pathfinding on directed graphs. *Proceedings of the International Conference on Automated Planning and Scheduling*, 30:212–216, June 2020. doi:10.1609/icaps.v30i1.6663.

[14] Alexander Kott, Ray Budd, Larry Ground, Lakshmi Rebbapragada, and John Langston. Building a tool for battle planning: Challenges, tradeoffs, and experimental findings. *Applied Intelligence*, 23(3):165–189, December 2005. doi:10.1007/s10489-005-4606-z.

[15] Hang Ma and Sven Koenig. Optimal target assignment and path finding for teams of agents, 2016. doi:10.48550/ARXIV.1612.05693.