Dear Dr. Jenkins, Many thanks for the comments from the editorial board members and four anonymous reviewers on the paper "Swarm Control for Distributed Construction: A Computational Complexity Perspective" submitted by myself, Ronald de Haan, Andrew Vardy, and Iris van Rooij. The reviewer and editorial board comments were summarized by Associate Editor 2 as follows: "This paper seeks to analyze the computational complexity of swarm control. The four well-qualified reviewers express a wide range of opinions about the paper. The reviewers collectively saw value in it. Each reviewer felt that the perspective of computational complexity in human-swarm interaction was welcome, important, and interesting. They feel this is a significant and neglected problem for which additional insights *can be* important to researchers in human-swarm interaction. The reviewers did have a variety of different concerns that I believe should be addressed. First, all reviewers provided a variety of recommendations for making the paper more understandable and assessable. Second, both reviewers 2 and 3 found the paper in its current form to have a rather narrow contribution. They were concerned that the way the proofs were constructed hurt the generality of the results. Reviewer 2 also felt the proofs should be better formulated to ``demonstrate the correspondence between its version of the problem & those in the literature.'' Third, reviewer 3 was concerned that the paper was not relevant to the HRI community, though reviewers 1 and 2 disagreed with this sentiment (and I agree with them). Finally, reviewer 2 felt that the current paper does not currently express good separation from prior work by the authors. I believe this paper has potential for being published in THRI, but believe the reviewers' comments need to be addressed thoroughly and satisfactorily before that is possible." We have revised our original paper in accordance with these comments. As requested, all revised text has been highlighted in boldface. Major changes are: * The addition of text describing the logic of computational complexity analysis, especially with respect to discovering frontiers of tractability for problems (Section 1). * The addition of a summary of previous work on distributed construction (Section 1.1). * A significantly revised and detailed description of the relationship of proofs and results in the current paper to those in our previous papers (Section 1.2). * Splitting of Section 2 into three subsections to allow more discussion of issues raised by the reviewers, in particular the relationship of the types of swarm control studied in the literature and the formalizations of swarm control investigated in our paper (Section 2.2). * Splitting of Section 4.1 into separate subsections assessing the completeness and generality of our results, with new discussion of the frontiers of tractability for swarm control implicit in our results (Section 4.1) and new discussion of the applicability of our results to swarm control relative to non-construction tasks (Section 4.2). Responses to specific reviewer comments are given below. Given the extensive nature of my revisions, we have not quoted revised text in these responses. Rather, where necessary, pieces of text in the revised paper that are particularly relevant to any Comment Y made by Reviewer X have been flagged in the revised paper with the tag "[RX(CY)]". Please note also that where references are cited in the reviewer comments, these references' numbers have been changed to those in the current rather than the original submitted manuscript. Ronald, Andrew, Iris, and I believe we have in the revised paper addressed all issues raised by the reviewers, and look forward to their and your respective thoughts on the revised paper. Sincerely, Todd Wareham -------------------------------------------------------------------------- Responses to Reviewer 1 Comments 1. p4l20: One might argue that poly-time approximate restricted solvability (as characterized by complexity classes such as BPFPT [1] or PPPT [2] can be consider efficient as well! [1] Montoya, J.A., Müller, M.: Parameterized random complexity. Theory of Computing Systems 52, 221-270 (2013) [2] Donselaar, N.: Probabilistic Parameterized Polynomial Time. Proceedings of SOFSEM 2019: 179-191 (2019) RESPONSE: We thank the reviewer for this most appropriate suggestion. Rather than mention these forms of tractability in Sections 1 or 3, we now mention them as a new direction to extend our complexity analyses in Section 5 in new text on page 25 flagged with the tag [R1(C1)]. 2. p7, l23: So they are part of the problem definition, rather than the input. Can the authors elaborate on their decision to make c1 and c3 constants, rather than inputs in unary notation; and how this might influence the complexity results? RESPONSE: We thank the reviewer for pointing out this oversight. On re-reading the original text, we erred on the side brevity; we have now given what we hope is a much clearer discussion on the factors underlying our decisions wrt c1 and c2 in new text on page 9 flagged with the tag [R1(C2)]. 3. p10l41: I do understand the relevance of explicating these results for the intended audience, but they are trivial corollaries of the NP-hardness of these problems and the assumption that P=BPP. I think it is fair to mention implicitly that A4 and A5 are corollaries of widely-believed complexity theoretic assumptions and not necessarily reveal great theoretical insights. RESPONSE: We thank the reviewer for this suggestion, which we have implemented in new text on page 13 flagged with the tag [R1(C3)]. 4. p12l45: I was a bit puzzled by this notation. This does mean the same as 'are in XP'? Or am I missing a subtlety? In either case it might be nice to comment on that in a footnote. RESPONSE: We thank the reviewer for pointing out this oversight. Yes, |x|^k-tractability is membership in XP, and this is now explicitly noted in a new footnote on page 13 flagged with the tag p[R1(C4)]. 5. p17l37: Just as an aside here: generalizing to probabilistic models invites using parameters that are not natural numbers (e.g., an error rate) which introduces various interesting consequences for the formal results, but might also generate interesting additional tractability results. RESPONSE: We thank the reviewer for this intriguing suggestion. We chose not to mention it in the current paper but will certainly consider it in our future research. 6, P2l41 this is a very complex sentence, consider breaking it down. RESPONSE: We thank the reviewer for this suggestion, which has been implemented with modified and new text on page 2 flagged with the tag [R1(C6)]. 7. On p3l14, it might be good to inform the reader at this point that this notation is not to be understood as 'number of elementary operations as a function of the input size' which would be the traditional computer science interpretation. RESPONSE: We thank the reviewer for this suggestion, which we have implemented in new text and a footnote on page 3 denoted with the tag [R1(C7)]. 8. p3l37 introduces a different concept relative to the cognitive complexity - emphasize to help the reader appreciate that these are different concepts. RESPONSE: We thank the reviewer for this suggestion, which we have implemented in a new footnote on page 3 flagged with the tag [R1(C8)]. 9. In p6l39 the symbol '*' appears without formal definition. RESPONSE: We thank the reviewer for pointing out this oversight. This has now been remedied with modified and new text on page 8 flagged with the tag [R1(C9)]. 10. p8l14: unsure about notation here? RESPONSE: We thank the reviewer for pointing out this oversight, which on re-reading we believe to be associated with our confusing notation wrt variables l and m. This has hopefully been clarified by modified text on page 10 flagged with the tag [R1(C10)]. 11. p9l25 insert such/these before issues RESPONSE: We thank the reviewer for pointing out this error, which has now been fixed with new text on page 11 flagged with the tag [R1(C11)]. 12. p9l42: I understand the definition, and the c1 constant is needed to cover for 'start-up costs', but I'm a bit unhappy with both the deviation from the traditional (asymptotical) big-Oh definition and the re-use of c1 and c2 here, as I think their interpretation is intuitively different than in (c1,c2) completion. RESPONSE: We thank the reviewer for pointing out these two oversights. We hope that both have been remedied (the former by explicitly noting the asymptotic nature of the runtime upper bound and the latter by replacing c1 and c2 with c and c') with modified and new text on page 12 flagged with the tag [R1(C12)]. We have also made corresponding changes acknowledging the asymptotic nature of the runtime upper bounds underlying fixed-parameter and |x|^k-tractability with new text on page 13 flagged with the tag [R1(C12)]. 13. p40l11 note the LaTeX typesetting error in RESPONSE: We thank the reviewer for point out this error, which has now been fixed. -------------------------------------------------------------------------- Responses to Reviewer 2 Comments Note that comments for this reviewer have been re-ordered and grouped together when the same point is being discussed. Places where this has occurred are denoted below by ellipsis (...). 1. First, it seems the contribution was built upon the authors' previous work in [62] and it is unclear what are the main incremental contributions developed in this paper ... By reading over [62], the reviewer found the discussed complexity analysis set-up in this paper is very similar to those in [62] and many results remain the same, e.g. p12 in this paper and p11 in [62]. It is suggested to clearly separate the contribution discussion in the introduction part and elaborate on the incremental contribution compared to [62]. RESPONSE: We thank the reviewer for this suggestion. The discussed complexity analysis set-up is indeed similar to those in [60] and [62] because problems DesCon and EnvDes in those papers are special cases of problems SelAlg and SelEnvInf in the current paper. That being said, the majority (close on two-thirds) of the results in the current paper are new and hence not merely incremental contributions compared to [60] and [62]. This is now described much more clearly in modified and new text on page 6 flagged with the tag [R2(C1)]. 2. ... there are no detailed formulations of the three computation problems: algorithm selection, environmental influence selection and leader selection, which should be critical to evaluate the effectiveness of the complexity analysis. ... [T]he lack of detailed explanation on the three problem set-up makes it difficult to understand the generality of the complexity analysis. For example, what are the transition model (dynamics) involved in each of the problems and what algorithms to use in order to construct the structure X in an environment? I could not find descriptions of the concrete swarm tasks until I read [62]. ... It is also unclear why the swarm control should be classified into the three types: algorithm selection, environmental influence selection and leader selection in the way defined in this paper. Common sense is that by switching the robot algorithm for each one of the swarm members, one could demonstrate the diverse roles for the robots (e.g. leader, follower) and the resulting environmental changes based on the position of the robot and the controller being executed. Moreover, in the robot leader selection problem in this paper, only the selected leader will be able to move, which is not the leader selection problem commonly studied in the community. The dependence between swarm members and leader/non-leader agents is not discussed at all, which is supposed to play a key role in the discussion of complexity. For example, as discussed in [28] the consensus swarm algorithm will have O(1) complexity and a robot team with linearly independent robot members will have O(n) complexity. Under the ill-posed problem set-up in this paper, the reviewer found the results very limited compared to other literature in the field, e.g. [28]. RESPONSE: We thank the reviewer very much for pointing out these issues. Wrt the formulations of our computational problems, we now realize that the relationship of swarm control methods to these problems was not clear in our original submitted manuscript. To remedy this, we have split the former Section 2 into Sections 2.1, 2.2, and 2.3, with Section 2.2 describing this relationship in much more detail. This detail points out that our problems are in fact generalizations of swarm control methods studied in the literature, and that such generalization is both a typical part of and has advantages when doing computational complexity analysis. This is now addressed by new text on pages 3, 9, 10, and 11 flagged with the tag [R2(C2a)]. While making these fixes, we also realized to our chagrin that the reviewer is quite right in pointing out that the construction task being modified by swarm control was not described in our original submitted manuscript. We hope this oversight has been corrected by the addition of new text on page 9 flagged with the tag [R2(C2a)]. Wrt our classification of swarm control problems and the possibility of simulating algorithm, environmental influence, and leader selection purely by algorithm selection, we agree that the latter is appealing on the grounds of mathematical simplicity. However, we have chosen to retain the three methods as they are part of the standard classification of swarm control methods in HRI and hence should allow a more obvious and easier connection of our results to results derived within the HRI community. This is described in new text (including Footnote 5) on pages 9 flagged with the tag [R2(C2b)]. Wrt our leader selection problem only allowing selected leaders to move, this is a very regrettable oversight in our original description of this problem -- in fact, all robot team members move, with leader members moving under human control and non-leader members moving as dictated by their controller algorithms. This is now clarified with modified and new text on pages 11 flagged with the tag [R2(C2c)]. Wrt to the lack of discussion of dependence between swarm members and leader/non-leader agents, this is an artifact of (1) our use of computational rather than cognitive complexity, whose results are not directly comparable (see new Footnote 2 in the main text of our resubmitted manuscript) and (2) our focus on numerical rather than structural restrictions for swarm control problems. This is further compounded by our focus on swarm control for distributed construction tasks rather than simpler tasks like consensus, foraging, and navigation commonly studied in the swarm control literature. That being said, our results do nonetheless have direct implications for swarm control for non-construction tasks; please see our response below to Comment 4 by this reviewer for details. 3. The provided discussion also requires a lot of preliminary knowledge from a number of other papers, hence making the paper not self-contained and difficult to read. ... The authors are strongly encouraged to give more details on the definitions used in the paper ... RESPONSE: We thank the reviewer for these suggestions, and empathize with their frustration that the paper is not self-contained and difficult to read on its own. The full details of the logic of computational complexity analysis in general and our model of robot team operation for distributed construction in particular are indeed manifold and presented over many technical publications by others and ourselves. This difficulty is compounded by the need to present this material in a reasonably concise yet comprehensible fashion to those in another subdiscipline of Computer Science (namely, Human-Robot Interaction). We have tried our best in the current paper to navigate between the twin perils of (self-)plagiarism and incomprehensibility by placing in the main text what we believe to be those details needed by HRI folk to understand the gist and significance of our analyses and results, and relegating all else to footnotes and the appendix with appropriate references to other work for those wishing further details. In those portions of text in the original submitted paper where reviewers believe we have erred particularly badly in this, we hope our modifications made in response to reviewer comments have fixed those errors (or at least clarified why we feel it necessary to make them) in the current submission. 4. The authors are strongly encouraged to ... connect the complexity analysis with concrete problem settings and candidate algorithms that help readers to better understand the use case and implications of the contribution. RESPONSE: We thank the reviewer very much for this suggestion. On re-reading our original submitted manuscript, we now realize that, in focusing on presenting and explaining results relative to swarm control for distributed construction, we neglected to discuss the implications of our results for swarm control relative to simpler non- construction tasks such as foraging, consensus, and navigation, which are the ones typically addressed in the swarm control literature. It turns out that on closer examination, our results have a much broader applicability to swarm control for non-construction tasks than we had anticipated --- that is, two thirds of our intractability results also apply to a basic navigation task and all of our tractability results apply to swarm control relative to all tasks. We hope that this is now adequately explained with new text on pages 20-23 and 25 flagged with the tag [R2(C4)]. 5. Another primary concern is that most of the proofs ... contextualized with specific values of parameters. Hence the generality of the results is questionable and the reviewer found limited insights from the provided results. ... In the provided parametric results in table 3 and 5 , there are certain specific numbers such as |f| = 38 for SA. 1 and |E_T| =6 for SA. 1. As a formal discussion for computation complexity, why are fixed parameters used in the theoretical reasoning? ... Another example is the Lemma A.7 in line 41 on page 27. Why is a particular instance with specific value discussed to represent the polynomial-time tractability, e.g. h=2, |Q|=1, d=3, etc.. RESPONSE: We thank the reviewer for pointing out this oversight. The goals of computational complexity analysis are not only to determine whether or not a specific problem is intractable but also to determine as tightly as possible what combinations of restrictions do and do not make a problem tractable. In the case of numerical-valued restrictions on problem parameters such as those given in Table 1 in the paper, it is thus of great interest to know those combinations of values for which intractability and tractability hold. We realize now that the logic underlying and the uses of so-called "frontiers of tractability" will not necessarily be familiar and hence needs explanation to those outside the complexity analysis community. We hope we have sufficiently remedied this with new text on pages 3, 4, 12, 19, and 20 flagged with the tag [R2(C5)]. 6. Almost all of the proofs in the appendix come from other papers with example-based explanations, which to the reviewer is inadequate. RESPONSE: We thank the reviewer for pointing out this potential misunderstanding. As noted above in our response to Comment 1 by this reviewer, we have now clarified the relationships between certain proofs in previous papers and certain proofs in our current paper such that it can now be seen (contrary to appearances) that the majority of proofs and results in the current paper are new. As for those proofs that either are straightforward adaptations of or build on previously-presented proofs, in order to avoid repeating the full details of previous proofs and committing self-plagiarism, we have chosen to give general descriptions of how the previous proofs operated (what we believe to be the "example-based explanations" referred to by the reviewer) followed by the changes required in the current paper. This has hopefully been made more explicit by new text on page 30 flagged by the tag [R2(C6)]. 7. [T]here are many notations used in the paper that are duplicate or never properly defined, which prevents the smooth understanding of the underlying concept. For example, in line 34-43 on page 6, what is f, x and *, and what does trigger-formula mean exactly? RESPONSE: We thank the reviewer for pointing out this problem. As was noted earlier in our response to Comment 3 above, we have in the interests of concision and avoiding self-plagiarism made choices in what material to repeat from previous papers and in what form. This is now explicitly acknowledged wrt definitions with new text on pages 6 and 7 flagged with the tag [(R2(C7)] (for similar choices made wrt the presentation of proofs, see our response to Comment 6 above). When specific examples are pointed out in which reviewers feel we have erred badly, we have endeavored to fix them. This is the case with the specific example above (also noted by Reviewers 1 and 4), which has now hopefully been fixed by modified and new text on page 8 flagged with the tag [R2(C7)]. -------------------------------------------------------------------------- Responses to Reviewer 3 Comments 1. Many (if not most) of the swarm behaviours are based on neighbours' interaction through communication. Removing communication from the problem is a big piece of what makes robotic swarms, and that is not solely related to communication latency problems. RESPONSE: We thank the reviewer for pointing out this potential misunderstanding. Though our robot team model does not allow direct robot-to-robot communication, it does allow basic indirect communication between robots via their sensed presences in and changes made to the environment, i.e., by stigmergy. This simplicity is in line with the other simplified aspects of our model of robot team operation. This is now hopefully clarified in new text on page 8 flagged with the tag [R3(C1)]. 2. The authors mention the need to restrict the model to use defined numerical values of c1 and c2, but they don't explain why and how they selected the values 3 and 10. RESPONSE: We thank the reviewer for pointing out this oversight. On re-reading the original text, we erred on the side brevity; we have now given what we hope is a much clearer discussion on the factors underlying our decisions wrt c1 and c2 in new text on page 9 flagged with the tag [R3(C2)]. 3. On pages 9 and 10, many results turn out to be inapplicable to the problem studied, but from the text it isn't clear why these results are quickly discarded. RESPONSE: We thank the reviewer for pointing out a confusing aspect of the original text. We do not discard the results on pages 9 and 10 (i.e., Results A.2-A.5) because they are inapplicable to the problems studied -- rather, these intractability results (which are relative to the general unrestricted versions of our problems) motivate our subsequent investigation of the types of tractability that do and do not hold for restricted versions of our problems. We hope that this has been clarified by new text on page 13 flagged with the tag [R3(C3)]. 4. The level of expertise required to clearly understand the methods and theoretical proofs is pretty high and requires a good grasp of all the theoretical works on which the authors based their work. For instance to cope with concepts that "are widely believed to be true within the Computer Science community". RESPONSE: We thank the reviewer for pointing out these problems. As in our response Comment 3 by Reviewer 2, we empathize with the reviewer's frustration that the paper is not self-contained and difficult to read on its own. The level of expertise required to fully understand our methods and proofs is indeed pretty high. To present this material in a reasonably concise yet comprehensible fashion to those in Human-Robot Interaction, we have chosen to place in the main text only those details that we believe are needed by HRI folk to understand the gist and significance of our analyses and results, and relegate all else to footnotes and the appendix with appropriate references to other work for those wishing further details. In those portions of text in the original submitted paper where reviewers believe we have erred particularly badly in our choices, we hope our modifications made in response to reviewer comments have fixed those errors (or at least clarified why we feel it necessary to make them) in the current submission. 5. The authors claimed to shed light on the real challenge of human-swarm interaction based on the theoretical derivation. The conclusion (to limit the operator degrees of complexity) is nothing new, even if the method to draw this conclusion is new. They use HSI work to show their finding can explain what was already observed. While this strategy is certainly interesting, it limits the scope of applicability of their finding. The reviewer suggests they conduct their own experiment to better support and illustrate their findings. RESPONSE: We thank the reviewer for this suggestion. We agree that, while being consistent with existing observations is useful (and a necessary first step in proposing new theories or theoretical approaches), our findings would indeed be better supported if we had the results of new experiments specifically designed to test these findings. Though two of us have experience with experiments (Vardy with robot swarms, van Rooij with human cognition), we do not have the necessary experience with human-robot experiments. If our complexity-theoretic approach turns out to be of interest to the HRI community, we look forward to collaborating with experiment-experienced HRI folk in future (a point noted implicitly in the last three sentences in Section 5). For now, in this paper, we prefer to focus on laying out as clearly as possible the nature of our complexity-analytic approach to HRI problems like swarm control and our mathematical results. -------------------------------------------------------------------------- Responses to Reviewer 4 Comments 1. I report a number of minor edits to fix typos and minor grammar issues: * P0:3L38: "designing such systems for tasks." -> remove the period * P0:4L17: "Leader Selection (SelAlg)" -> "Leader Selection (SelLead)" * P0:9L14: "for all intensive purposes" -> "for all intents and purposes" * P0:9L37: "meaning of and patterns in of" -> rephrase * P0:10L15: "polynomial-time promise solvable" -> not clear what "promise" means here * P0:11L37: "four easily-proven lemmas" -> "four lemmas" * P0:17L26: "intractability results" -> add period * P0:18L13: "in this endeavor" -> add period * P0:18L33: double period at the end of the line RESPONSE: We thank the reviewer for pointing out these errors; they have all been fixed on pages 5, 12, 13, and 14 flagged with the tag R4(C1). In the case of the fifth suggested edit, promise solvability was actually defined several lines previously but not in an obvious fashion. This has been remedied by putting ``polynomial-time promise solvability'' (and, several paragraphs later, ``polynomial-time approximate solvability'') in boldface to make it stand out. 2. A few symbols are used before they are formally defined. For example n at line 13 of page 0:3 and h at line 39 of page 0:4. RESPONSE: We thank the reviewer for pointing out these oversights. The first of these is remedied with a new footnote on page 3 flagged with the tag [R4(C2)]. The second has been eliminated courtesy of the changes made wrt Comment 4 below. 3. The meaning of the * symbols at page 0:6, line 39, is not defined and was not clear to me. RESPONSE: We thank the reviewer for pointing out this oversight. Symbol * is a special symbol whose meaning is now hopefully clearer courtesy of new text on page 8 flagged with the tag [R4(C3)]. 4. I appreciate the effort made in Section 1.2 to provide a quick glance at the main results offered in the paper. I enjoyed most of this section, but I found the discussion in the bullet points quite hard to grasp (lines 39-onwards of page 0:6). This was due to the symbols being used before definition, and to the excessively formal tone of the text. I would suggest to provide a more descriptive summary, or at least more verbose one, to make the main points more easily understandable. RESPONSE: We thank the reviewer for bringing up this concern. We want to be sure to accurately describe our results, so a formal tone is necessary. That being said, we have have eliminated the use of symbols prior to definition and tried to be a bit more verbose in our descriptions via modified and new text on page 5 flagged with the tag [R4(C4)]. 5. The title of the paper mentions "distributed construction", but this theme is marginal in the paper. I understood that the construction angle stems from the ability of the robots to modify their surrounding grid cells; however, the paper lacks a dedicated subsection in Section 4 that justifies the use of catchy keywords such as distributed construction. I would suggest the authors to drop these keywords in the title, or to explicitly add a discussion section on this topic. RESPONSE: We very much thank the reviewer for this suggestion. The focus in our paper is admittedly on swarm control methods, with distributed construction being an application of these methods. Inspired by this reviewer's suggestion, we conducted additional literature searches and realized that human-robot collaboration in construction is an increasing focus of research. Indeed, a very recent review (published in November 2021) [20] has proposed a new research area, Collective Human-Robot Construction. Given that swarm control is still the main focus of the paper, instead of adding a discussion in Section 4 as suggested by the reviewer, we have chosen to add a discussion of previous work on distributed construction in Section 1.1 and a mention of this work as a future research direction in Section 5. This has been done in new text on pages 4 and 26 flagged with the tag [R4(C5)]. 6. How were the values c1=10 and c2=3 chosen? RESPONSE: We thank the reviewer for pointing out this oversight. On re-reading the original text, we erred on the side brevity; we have now given what we hope is a much clearer discussion on the factors underlying our decisions wrt c1 and c2 in new text on page 9 flagged with the tag [R4(C6)].