Enhancing Robot Program Synthesis Through Environmental Context
Authors: Tianyi Chen
Qidi Wang
Zhen Dong
Liwei Shen
Xin Peng
Venue: NeurIPS 2023 poster (2023)
Keywords: program synthesis
partial envrionment
robotic programming
domain-specific language
TL;DR: We present a framework that learns to synthesize a robot program by rectifying potentially erroneous code segments, with the aid of partially observed environments.

Abstract: Program synthesis aims to automatically generate an executable program that conforms to the given specification. Recent advancements have demonstrated that deep neural methodologies and large-scale pretrained language models are highly proficient in capturing program semantics.
For robot programming, prior works have facilitated program synthesis by incorporating global environments. However, the assumption of acquiring a comprehensive understanding of the entire environment is often excessively challenging to achieve.
In this work, we present a framework that learns to synthesize a program by rectifying potentially erroneous code segments, with the aid of partially observed environments. To tackle the issue of inadequate attention to partial observations, we propose to first learn an environment embedding space that can implicitly evaluate the impacts of each program token based on the precondition. Furthermore, by employing a graph structure, the model can aggregate both environmental and syntactic information flow and furnish smooth program rectification guidance.
Extensive experimental evaluations and ablation studies on the partially observed VizDoom domain authenticate that our method offers superior generalization capability across various tasks and greater robustness when encountering noises.

Enhancing Robot Program Synthesis Through Environmental Context
Tianyi Chen
Qidi Wang Fudan University 212102400380m fudan. edu. on
Fudan University tianychen21 @m. fudan. edu. cn
Zhen Dong
Liwei Shen
Xin Peng
Fudan University
Fudan University
Fudan University
zhendong@fudan, edu.
shenl @henliwe@ffudat edu. cn
pengxin&fudan edu. cn
Abstract
Program synthesis aims to automatically generate an executable program that conforms to the given specification. Recent advancements have demonstrated that deep neural methodologies and large-scale pretrained language models are highly proficient in capturing program semantics. For robot programming, prior works have facilitated program synthesis by incorporating global environments. However, the assumption of acquiring comprehensive understanding of the entire environment is often excessively challenging to achieve. In this work, we present framework that learns to synthesize program by rectifying potentially erroneous code segments, with the aid of partially observed environments. To tackle the issue of inadequate attention to partial observations, we propose first learn an environment embedding space that can implicitly evaluate the impacts of each program token based the precondition. Furthermore, by employing a graph structure, the model can aggregate both environmental and syntactic information flow and furnish smooth program rectification guidance. Extensive experimental evaluations and ablation studies on the partially observed VizDoom domain authenticate that our method offers superior generalization capability across various tasks and greater robustness when encountering noises.
Introduction
Program synthesis endeavors to produce an executable program that fulfills the prescribed specifica- tions. Given that formulating definitive and lucid specification often prove more arduous than physically authoring the program, a widely-used method is furnish input/output (I/O) examples as close approximation of the requisite specification [16. 17 27 34] also known Programming By Example (PBE). allows a more straightforward presentation of the desired program functionality, The utilization of PBE enables machines acquire the capacity implicitly capture set of regula- tions and generalize them to analogous scenarios. Over the past few years, PBE has demonstrated its remarkable potential elevate automation and ease human labor in numerous domains, including but not limited to array transformation demonstrations
46 56 graphic design [6]] and comprehension of human
21 42).
In the realm of robot programs, erucial factor is the interaction between the robot and its environment. In practice, robot can solely rely its sensors to perceive the environment by gathering diverse types of data, which forms the basis for every decision. Consider a robot designed for food delivery,
Cooresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

which is tasked with transporting food to a specified destination. The robot is faced with a decision between two paths: one that is obstructed by barriers and leads to dead-end, and another that is more circuitous and distant. If the robot is furnished with comprehensive knowledge of the environment, may be possible to create a simple program consisting of only a few actions. However, if the robot can only obtain partial observations, such as RGB image data from its current perspective, a more intricate program with sophisticated control flow may be necessary to navigate out of the dead-end and reach the intended destination. Consequently, the latter program can generalize better in accomplishing more complex tasks. The variation in the level of observation can significantly impact the ultimate outcome. Therefore, the challenge in robot program synthesis arises from the fact that robots are limited to partial observations of their surroundings, making it difficult to assess the global impact of the generated program tokens toward the desired output. This is due to the fact that a comprehensive understanding of the environment is not achievable.
At present, there exists diverse range of deep learning techniques aimed at solving PBE problems using neural network models [ g 32] Empirical studies 3 [ have shown that recurrent neural network (RNN) architectures can learn strategies that generalize across problems and remain robust to moderate levels of noise. However, these methods have limitations in their ability to effectively utilize environmental observations due to their reliance on the RNN as the backbone. Additionally, recent studies have introduced reinforcement learning 7 28). debugger method [19] and latent generative methods [10 48 into the field. Furthermore, other studies have revealed that incorporating intermediate states produced by executing partially generated programs can improve the capability to
address program synthesis tasks, especially for sequential programming tasks ( 43 47 [56). These techniques have primarily been evaluated on the Karel 112 possesses complete awareness of the entire environment. To clarify, even if particular location in the environment is inaccessible or unknown to the robot, the model can still generate a program with knowledge of that spot. Nonetheless, this assumption of acquiring global view of the environment is arduous to achieve in reality, and their aptitude to generate accurate programs with only partial observations remains to be explored.
18 44 dataset, in which the model
To tackle this issue, we introduce our novel Envirommental-contern Validated LAtent Program Synthesis framework (EVAPS). Drawing inspiration from the successful previous work SED [19], as well as the current trend of large language models [T 22 23], we believe that the trail-eval-repair loop provides valuable guidance for the evolution of programs, leading to better generalization ability. In order to leverage partial environmental observations, EVAPS initially obtains candidate programs by employing the same neural program synthesizer component used in SED. Subsequently, by executing the candidate program, EVAPS acquires the partial environment before and after each action (i.e. the environmental context). By concurrently modeling both the environmental and syntax contexts, EVAPS iteratively alters the programs that do not produce the correct output in an effort to resolve semantic conflicts across program tokens, ultimately correcting erroneous program fragments.
The framework was assessed in the partially observed VizDoom domain [24 [55), where a robot oper- ates in 3D world and interacts with its environment, including objects and adversaries. The results of the experiment demonstrate that the proposed approach is superior in modeling program semantic subtleties and resolving potential errors, thereby enhancing its generalization ability. Additionally, we authenticate the efficacy of leveraging environmental contexts and aligning them with code syntax by carrying out an ablation study. Further experiments show that our method is more capable of solving complex tasks compared to prior works. Furthermore, we validate that our method remains robust when encountering various levels of noise.
2 Problem Formulation
In a typical PBE task, we are given a set of N training samples, represented as [TO)* p)"
Each sample consists of K 1/O pairs that act as specifications, and a gold program P that correctly maps the input state to the output state O, such that P(I+)) + Of. where Vi E [1, Vk [1, K]. Previous studies have investigated techniques synthesize candidate program Po solely based on I/O. Our objective is to train neural model, denoted as G. which takes a candidate program P, and the corresponding environmental contexts O obtained by executing the program P. as an input. The model generates a refined program by incorporating environmental contexts: G(P, O) + PS, such that the mapping of program P* (/) approaches more closely to P(I) given input I. To assess the

---

6
Refined Program Tokens
MLP
Softuma
Decoding
def run():
LSTM
ifelse inTarget demon:
attack()
else:
moveLeft()
A-?
Candidate Program
Convolution
Graph Attention
M
R2
ng
A2
AC
A5
A1
lifbse
Vizdoom
Node Embedding
Program Graph A Attention
Interpreter
(b)
inTanget
attack
Demon
eise
moveLeft
Candidate Program Graph
P Program Segments
Figure 1:
The EVAPS architecture proposed involves the preprocessing of the candidate program into program graph, which can be further utilized for code segment generation and code symbol representation learning. The encoder comprises (a) the partial observation leveraging module that utilizes insights gleaned from partial observations by learning latent environmental context representations, and (b) the code symbol alignment module that brings richer semantic features by aggregating neighbor syntax symbol representations. Eventually, the decoder outputs refined program tokens by incorporating both modules.
generalization ability of the model G, we include another set of held-out examples that not part of the training samples, denoted as {10} Kicat, enabling us to measure the equivalence between p and P using 10 {IO}* UfIO) Keas
Methodology
3.1 Leveraging Partial Observations
In the VizDoom domain, the robot perceives its surroundings O by collecting an RGB image On E Ia xww xnc and depth buffer OD Ro xxwxl from its visual perspective, denoted as O = (OR, Op). This forms its partial observation of the world. By executing a program, we can obtain sequence of observation changes O executed action, denotes the number of total execution steps, and On denotes the initial observed state. As depicted in Figure [a), the hidden environment representations can be learned by applying convolutional network layers, and the embedded vector at the /-th layer can be denoted as:
06
DCng O where ac; refers to the i-th
R
n
nw
! 2.9
CoCCCoCCCC (onn(O K) = glll
ΣΣ
Ki,a.ee
11--1 #+th 1ith-lytw-i:
where K represents the convolutional kernel, and gd signifies the activation function at layer i,
To effectively utilize insights gleaned from partial observations, it is essential that obtain the antecedent states Opre (also known as the precondition) and the potential consequent effects O Opost corresponding to each token of program P. that the model can implicitly evaluate whether this token contributes towards completing the task in current context, determine whether substitution with another token would heighten the likelihood of task fulfillment.

---

Given that only those tokens that denote robot actions (e.g., moveForward) have the potential to alter the environment, whereas other tokens function as constituents of particular statement (e.g.. i and wh 1e), straightforward voken-by-token modification strategy appears unappealing. Since non-action tokens cannot exist independently and can only render code block semantically complete when they co-occur with action tokens, we deem it more fitting to process them unified segment.
We define a segment as triplet comprising of S (cond, token, body). Here, cond refers the condition of the segment, and body denotes the associated actions or subsegments. In the case of an action token, the segment form deteriorates into parsing the abstract syntax tree of program P. we can eventually yield a collection consisting of T' program segments, denoted ST. And by executing program segment S, ST using the VizDoom interpreter, we can acquire the post-segment effect with Execcte Pre) + O Opsst thereby obtaining the environmental context (Opre: O (poa)) of segment St, presented in Figure | The interconnection between the observable world state change and the code segment promotes greater semantic versatility, which, in turn, enables the model to calculate the probability of substituting each token based on the partial environment, resulting in the following formulation:
(nall, action, rull). By recursively
L1
CLe O postt )
Po (Pir Opres Opost) = II
II Po (c.le,,.., \==1
Cst1, (11,,,
S.EST
where Le denotes the number of tokens in segment S,, e, refers to the s-th token of segment S,, and 6, represents the refined program token that substitutes eg. To optimize the model parameters, the objective is to minimize the cross-entropy loss, given N training examples, where S represents the program segment set the i-th example, which contains T2 segments:
N
L=
1
log (po(s]le,...., 6x-1, Extls ELey Ol pres )past)
(3)
N E
T,
L
S,ES,
s=1
3.2 Code Symbol Alignment
Now that the environmental contexts have been obtained, they are currently paired separately with their own code segments, and the correlations among environmental contexts are not fully exploited. Relying solely on partial observation insufficient for the model comprehend the semantic and syntactic long-range connections of program tokens, making it arduous for the model to consolidate information that traverses through subsequent segments during the program repair process. Further- more, with regard to program syntax, the inherent nature of program necessitates the model to jointly reason over code symbols, such as types. For instance, the code while (turnLeft) syntactically incorrect because t turnLeft is an action rather than perception, which is prohibited to follow while. Therefore, it is desirable to align the code symbols with the partial observations to facilitate more comprchensive information flow.
To accomplish this, we first construct a program graph G C x (presented in Figure T to represent each candidate program P. where V denotes the set program token nodes and E denotes the set of undirected edges. Subsequently, we employ graph attention 6 50) for each token to capture a contextualized representation. Similar to the definition of a segment, each node within the program graph possesses leftward pointer that directs towards nodes signifying conditions, and rightward pointer that indicates a subsequent token node. The node's 's value encompasses the token index, and token type. Meanwhile, the relationship between tokens and their corresponding segments is stored. In this way, we not only align the code symbols and environmental contexts but also aggregate further semantic and syntactical representations. Additionally, it enables the model to effectively capture the nested structure of a program, thereby bringing more expressiveness.
To elaborate, we begin by obtaining the node representations h; R& for each node V, E G through embedding. Subsequently, a scoring function a IRd I + R is employed to compute the attention score of its neighboring node Vy. This score reflects the significance of neighbor node. The attention scores are then normalized across all neighbors j E N, using softmax, which defined as:
exp A LeakyReLU(W [hallha])
a: ah,; h1) EmENIUR) exp LeakyReLUUW (/.b (h.](/u]))

---

where A and W are weight matrices that can be learned, and represents vector concatenation. As result, node Vi acquires new representation by calculating the weighted mean of the modified features of its neighhoring nodes, as illustrated in Figure[b)
h Oiia Wh; + Σ otj" Whj.
(5)
JEN,
Next, we can obtain the corresponding environmental embedding of the token V; through O Conv(O, K) (Eq. (T) To align the code symbol representations and environmental contexts, we update the representation of node V, by simply concatenating these embeddings x; = [h]][O]]. This leads to modification to Eq.
L1 II po (<i)zs)) 1==1
Pe(Pin ( O Opost)
II S.EST
(6)
The key connection between the proposed approach and observable environments resides in establish- ing a connection between the program execution context and the partially observable environment. EVAPS takes the exccution context of segment S and the corresponding partially observable en- vironment as a unit for model training. This enables the combination of program syntax and the corresponding partially observable environment to predict token, thereby enhancing the accuracy of program synthesis. As result, the model can adeptly resolve the underlying conflict within program by concurrently capturing well- well-integrated and highly pertinent semantic and contextual patterns, culminating greater practicality of programs.
4 Experiment
4.1 Experimental Setup
VizDoom Domain. The programs in this study are structured using Domain-Smeoniee Speciffc Lan- guages (DSL) in the VizDoom environment [4]. This environment provides 3D world that closely resembles real-world scenarios, al- lowing the robot efficiently perceive, in- terpret, and learn the 3D realm. In recent times, there has been burgeoning interest in VizDoom exploring the robot's capabilities make tactical and strategic determinations [1] 25 41 47 (53) The VizDoom exper- imental environment consists of 7 action prim- itives, 6 perception primitives, and the state rep- resentation dimension 120 x 160 x 3. The average number of steps required to complete tasks is 4.6. We contend that the VizDoom environment more suitable for robot program syn- thesis research compared to Karel, due to its limited partially observed nature (55), which renders decision and execution process more realistic and practical the robot. The DSL comprises actions, perceptions, and control flows, sufficient to encapsulate the fundamental concepts of robot programming. The detailed description is presented in Figure 2]
Program m run0: :
Statement whilo(b) (s) $1 repoat(r) (s)
if(bb : (s) ifeels(b) (s,) else (s2)
Repetition r= Integer number of repetitions
Condition == perveption y not
Action moveForward moveBackward moveLeft
moveRight tumLeft tumRight attack
Perception y isThere e inTarget
Monster ::= demon hellK | revenant
The Nomain-Speccine Language (DSL) for Vizdoom programs comprises action primitives, perception primitives and control flows.
Figure 2:
Dataset. To generate dataset for learning environmental-conter embeddings, we adopt the same approach as previous studies 14 47], randomly generating 100, 000 distinct samples. The dataset then partitioned into training set with 70, 000 samples, a validation set with 20, 000 samples, and testing set with 10, 000 samples. We adhere to the program synthesis conventions [9]. where each sample includes correct program, 5 input-output pairs that act as specifications, and an extra input-output example as the test sample, which solely employed for evaluation purposes and not for training. During the generation process, we also conduct checks to ensure that all execution branches in the program are covered at least once, thereby representing aspects the program's ''s behavior and providing sufficiently challenging tasks.
5

---

Table 1: The average accuracy (with standard deviation) of all methods evaluated on three metrics across Vizdoom tasks, assessed over 5 random seeds. The best results are highlighted bold.
Methods
Exact Match
Semantic Match
Generalization
LGRL 77
2.18% (0.34%)
33.42% (1.12%)
31.49% (1.26%)
SED [99
12.69% (0.55%)
43.07% (0.57%)
38.63% (0.51%)
Inferred Trace
43
14.73% (1.73%)
36.87% (1.81%)
35.09% (1.73%)
Top-1
Latent Execution
10
3.53% (1.12%)
44.40% (2.31%)
42.25% (2.22%)
Transformer 44
15.53% (1.75%)
26.51% (1.96%)
25.93% (1.77%)
EVAPS (Ours)
36.40% (2.52%)
50.29% (2.18%)
48.90% (2.23%)
LGRL 77
4.58% (0.43%)
54.25% (1.01% %)
51.56% (1.08%)
SED
[19
25.48% (0.89%)
66.76% (0.92%)
62.25% (0.65%)
Inferred Trace
43
27.49% (1.87%)
55.13% (0.59%)
52.80% (0.88%)
Top-5
Latent Execution 10
4.91% (1.32%)
50.76% (2.07%)
48.62% (1.81%)
Transformer 49
34.80% (4.23%)
47.96% (2.24%)
46.76% (2.13%)
EVAPS (Ours)
50.62% (2.07%)
99.82% (1.72%)
67.82% (1.81%)
LGRL 17
9.16% (0.76%)
66.22% (0.19%)
63.49% (1.06%)
SED
51.23% (1.01%)
71.42% (3.66%)
67.06% (3.76%)
Inferred Trace 43
37.75% (2.10%)
66.69% (1.82%)
63.96% (1.54%)
Top-20
Latent Execution 110
9.16% (1.21%)
59.93% (1.96%)
57.53% (1.50%)
Transformer 49
51.53% (3.61%)
64.69% (2.90%)
63.09% (2.77%)
EVAPS (Ours)
62.22% (3.28%) 79.20% (1.08%) 76.84% (1.13%)
Evaluation Metric. To comprehensively assess the capability of synthesizing programs based on provided inputs and outputs, we evaluate all models using three metrics: (1) Exact Match. It considers generated program to be an exact match if every token in it is identical to the gold E E== & (TTKN,
program. This is expressed mathematically where TKN, (P+,) refers to the t-th token of program P., Φ yields 1 if the condition is satisfied and 0 otherwise, and L denotes the length of the program. (2) Semantic Match. It takes into account that a synthesized program may be semantically equivalent but not syntactically identical to the gold program. This metric is expressed as: Σ (1,; P.( = O VIA O E {10}, (3) Generalization Match. To genuinely evaluate the generalization ability of a model, it is crucial to assess its ability to generalize on unseen samples in addition to semantic consistency. To achieve
TKN, Vt e [1,
this, we include additional examples and evaluate the model's performance as: Σn @/P; P.(TT) O+). VT& Of e (TO} ( Kenet Kindly note that our primary concern regarding the model's 's performance is the metric of generalization match.
4.2 Results
Overall Synthesis Performance. T the primary outcomes of our EVAPS in comparison to prior works [0 43 for VizDoom program synthesis. Notably, we have implemented beam search technique for Inferred Trace, Latent Execution, and Transformer to enable the generation of multiple candidate programs while preserving their original architecture. Additionally, we have incorporated convolutional neural network top of the Transformer to facilitate the learning of specification embedding, given that the specification is in the form of grids rather than sequences, and the Transformer serves as the decoder. The supplementary material contains the detailed parameters of all the compared methods.
We can observe that EVAPS consistently outperforms other methods across three metrics, with an approximate improvement of +9.6% compared to the runner-up. This indicates its superior capability to resolve potential semantic errors by incorporating environmental contexts, thereby enhancing its generalization ability while preserving syntax modeling ability. Moreover, EVAPS surpasses SED primarily due to the fact that SED only enhances program tokens based on execution outcomes and

---

Table 2: The average accuracy (with standard deviation) of all ablation methods evaluated on three metrics across Vizdoom tasks, assessed over random seeds. The best results are highlighted in bold, and Gen.A represents the mean improvement in generalization match.
Methods
Exact Match
Semantic Match
Genralization
Gen.A %
Naïve
3.42% (1.80%)
32.29% (5.41%)
30.29% (5.36%)
EVAPS+0
23.56% (5.02%)
46.80% (2.53%)
45.24% (2.49%)
+14.95%
Top-1
EVAPS+S
23.42% (1.84%)
42.47% (2.87%)
41.09% (2.79%)
+10.80%
EVAPS
36.40% (2.52%)
50.29% (2.18%)
48.90% (2.23%)
+18.61%
Naïve
7.38% (3.15%)
52.11% (1.10%)
49.60% (1.50%)
EVAPS+O
40.15% (4.52%)
61.49% (1.85%)
59.71% (1.72%)
+10.11%
Top-5
EVAPS+
40.90% (4.80%)
58.18% (3.42%)
56.58% (3.20%)
+6.98%
EVAPS
50.62% (2.07%)
69.82% (1.72%)
67.82% (1.81%)
+18.22%
Naïve
12.87% (3.25%)
64.80% (1.56%)
61.96% (1.57%)
EVAPS+0
55.35% (4.90%)
71.60% (2.54%)
69.63% (2.22%)
+7.67%
Top-20
EVAPS+S
56.29% (5.26%)
69 69.85% (2.79%)
67.78% (2.56%)
+5.82%
EVAPS
62.22% (3.28%)
79.20% (1.08%)
76.84% (1.13%) +14.88%
specifications, whereas EVAPS places greater emphasis the semantic locality, supplemented by utilizing partial observations. While the attention mechanism of Transformer facilitates its ability to learn syntax, its generalization ability is relatively poor. Although LGRL can achieve comparable results terms of generalization, it faces challenges in producing program sequences that are identical to the gold programs due to its tendency to generate semantically equivalent programs in a more complex environment. Inferring traces can provide information gain, but the partially observed environment restricts the model from capturing subtle semantic features. This limitation also applies to the latent executor, as the global status becomes agnostic to the model, thereby limiting its ability to extrapolate the exccution states and learn the latent effects of each token.
Ablation Study. To thoroughly verify the efficacy of the partial observation leveraging module and the code symbol alignment module of EVAPS, perform ablation study authenticate their capabilities and scrutinize their impacts as Table presennss We consider the following ablations:
Naïve: variation of the program synthesis baseline LGRL [7] that utilizes greedy decoding (i.e., implements a beam search with beam size = 1). It employs a standard encoder-decoder architecture that acquires the ability to directly synthesize program from scratch.
EVAPS+O: an ablation of EVAPS incorporating partial environmental observations to modify
tokens and resolve semantic conflicts in synthesized programs.
EVAPS+S: an ablation of EVAPS aggregating long-range semantic and syntax connections of neighboring code symbols.
EVAPS (EVAPS+O+S): incorporates both modules, allowing for a more comprehensive informa- tion flow and leveraging environmental context facilitate program synthesis.
Based on the ablation outcomes presented Table 2 we can deduce that utilizing only partial environmental observations or code symbol alignment can enhance the joint semantic and syntax modeling ability. However, the information gain is limited if only one of these techniques is employed. This is because the former concentrates primarily on the environmental context of particular token, disregarding the implicit connections between different code segments in semantic spaces. On the other hand, the latter focuses mainly information aggregation rather than environmental contexts. Consequently, combining these techniques can endow the model with supplementary information and further boost the program synthesis process, resulting in an approximate enhancement of +16% in terms of generalization.
Task Complexity. Considering the varying complexities of different robot tasks, generating corresponding codes to accomplish them may pose varying levels of difficulty. Hence, we endeavor to delve deeper into the efficacy of each method in handling diverse levels of complexity. The issue of program aliasing, wherein two programs are semantically equivalent but not identical (e.g.. while (r=3)= turnLeft and turnRight), renders the evaluation of complexity using program
7

---

Steps
Steps
Steps
Generalization (%)
80
70
60
50
40
30
20
Steps = 5
Steps
Steps = 7+
Generalization (%)
80
70
60
50
40
30
20
5
10
15
20
1
5
10
15
20
1
5
10
15
20
Top-K
Top-K
Top-K
LGRL
Inferred Trace
Transformer
SED
Latent Execution
EVAPS (Ours)
Figure 3: The generalization capability of methods ranging from Top-I to Top-20 evaluated across six categories that were partitioned based on the minimum number of steps required to complete the task. The tasks that can be accomplished with least seven steps were denoted as 7+,
length or control flow presence imperfect. Hence, we propose partitioning the tasks into different complexity levels based on the minimum number of steps required to complete the task, which we denote as steps.
To be specific, we have divided the testing set into six distinct categories based on their level of complexity, with each category requiring 3, 4, 5, 6, or 7+ steps complete, respectively. The 7+ category is reserved for tasks that demand no fewer than seven steps to accomplish. We then proceed train and evaluate the model's performance in each category separately, and the results of this analysis are presented in Figure Firstly, it is evident that as the complexity of the task increases, all methods experience certain degree of performance degradation. This is reasonable since the embedding space becomes more intricate to learn as the task becomes more complex. Furthermore, we can infer that the performance gap between EVAPS and other methods widens as the complexity increases. This suggests that EVAPS is better equipped to adapt more intricate tasks, owing to its ability break down complex objectives into simpler behaviors by leveraging partial environmental contexts. On the other hand, the modeling ability of Latent Execution becomes relatively inferior, particularly for Step=7+, which indirectly implies that it challenging for a model to deduce the impact of complex behaviors in single attempt.
Interestingly, for most techniques, the ability generalize experiences surge approximately the Top-5 candidate programs. However, the rate of improvement tends to decelerate and the curve becomes flat. We surmise that this phenomenon occurs because certain semantic representations are conspicuous and uncomplicated to acquire, whereas others are more nuanced. Even with more candidate programs, the semantic features corresponding to these programs are somewhat overlapped, thereby reaching the limit for capturing semantic subtleties and hindering further generalization.
Handling Noisy Observations. For robot programming, real-world observations collected through sensors in real-time, making it inevitable for occasional noise to occur. Consequently, we tend to evaluate the ability of our method handle such noise. Given that the VizDoom dataset lacks noisy examples, we artificially introduce noise into the dataset by invalidating certain percentage of observation grids based on uniform random probability [5]

---

The results regarding different levels of noise (with a maximum noise of 20%) are illustrated in Figure 4 It can be inferred that the presence of noisy observations inevitably undermines the capacity of EVAPS to learn program semantics and generalize. Nevertheless, EVAPS still man- ages to exhibit decent modeling ability, If we consider all Top-K potential candidates, the maximum performance drop obtained is merely about 7.5%. Meanwhile, with fewer candidate programs, the performance gap widens, but it is bound to be 12%. This outcome aligns with our expectations, thus we conclude that EVAPS capable of recognizing significant semantic patterns and maintaining robustness when countering noises.
Generalization (%)
70-
60
50-
40
5
10
15
20
Top-K
0% -4-- 5%
10%
15%
-d.: 20%
Figure 4: The generalization capacity of EVAPS in the presence of diverse levels of noise, accom- panied by 95% confidence interval band.
Dicussion. The partial observation that the proposed approach relies on is often available in practice, thus is theoretically feasible to apply this approach to the real world. Certainly, we anticipate some practical difficulties during the transition from the simulation environment to the real world. For instance, can be labor-intensive to collect enough environmental data from the real world for the purpose of training. Further investigation into the efficient acquisition of environmental data while sustaining its quality is yet to be explored in future works.
Related Work
Programming By Example. In the realm of program synthesis, the synthesis of programs from examples has long been a preoccupation of researchers. In recent years, deep learning methods have made many breakthroughs [37 [13 36), and many researchers have proposed different methods for Improve the accuracy of synthesis. Symbolic search is regarded as an efficient technique for addressing program synthesis challenges 40 38 ST 26]. Wang et al. have devised language for abstract queries, which facilitates the generation of SQL [5T]. Moreover, Spoc has recognized the significance of pseudocode and explores its potential for aiding code search, focusing on alternative translations of pseudocode (26). While symbolic search can yield promising outcomes within specific training domains, it lacks the ability to expand, and it is relatively hard to generate code snippets beyond the training datasets.
To tackle the issue of code fragment homogeneity, two approaches have gained prominence: the utilization of hidden variables and the employment of reward mechanisms. In order effectively utilize the information contained in latent variables, some researchers consider using latent generative models (3] 10 48). Aim obtaining the intermediate execution results of partial programs in C language, Chen et al. approximate by learning the latent representation of partially generated programs to facilitate program token search 10] Additionally, reinforcement learning has been integrated into synthetic neural network training in numerous studies 7 [6] 48 19. Bunel et al. combined program synthesis with reinforcement learning 77) and avoided the problem of Program Aliasing by defining proper rewards; Trivedi et al. considered two-stage learning scheme on this basis [48. First, a program embedding space learned in an unsupervised manner, and then the most suitable program is searched in the embedding space with given reward.
In our approach, we also use a reward mechanism for generating candidate programs. However, we extend this by adopting the concept from SED [19] to train an evaluator that assesses the candidate programs for further repair. While both EVAPS and SED incorporate environmental observation to train the neural program debugger, there are notable distinctions between the two: i) The execution feedback of SED relies on global perspective, which is only available in some special cases. Conversely, EVAPS embraces partial observation, which is more achievable in real-world scenarios. ii) SED treats the program as a whole for training, while EVAPS pays more attention to the execution context. iii) EVAPS establishes connection between the program execution context and the partial observable environment. Distinguishing itself from SED, EVAPS places greater emphasis on the partially observable environment in which the robot operates and the local context of the program.

---

We believe that this approach enables the network to concentrate more precisely on the actual scope of the impact of the program.
Program Repair. Program repair has also been a widely researched topic. Most researchers pay attention to the grammatical features 30 29 45
and semantic information 52 54 of programs. Rolim and Hua [39 20 employ abstract syntax trees to derive effective outputs, while Tlix 4 treats programs as text and trains a general Transformer model for repairs. While these approaches have achieved breakthroughs in different problem domains, they often overlook the semantic aspects of programs. Wang et al. address this by incorporating the learning of semantic embeddings from program execution trajectories [52], while Ye et al. enhance neural networks using a loss function based on program compilation and execution information [54]. Our work takes both semantic and grammatical information into account. Our evaluation network, which is based on the execution information of the program in the environment and the program's 's grammar domain-specific language, can effectively accomplish program repairs.
Regarding traditional program repair approaches, we are aware of branch of rich works in the program repair area, which can be classified into three categories: i) Search-based This type of approach considers program repair as a search problem, exploring the space of all possible program candidates to identify one that satisfies the given weak specification, i.e., test cases. One of the prior works in this area is GenProg [1. ii) semantic-based. This type of approach extracts semantic information from the program under repair (typically represented as path constraints) and then generates patches by solving those constraints. A well-known work is SemFix (35]. iii) Learning- based. This type of approach leverages a number of patches generated by developers to learn a model that repairs programs. An earlier work is Prophet (33.. Those approaches depend on high-quality test suites to validate patch candidates, which are unavailable in the setting our approach is targeted at, ie.. VizDoom.
6 Conclusion
This paper introduces EVAPS, a novel approach to augment the applicability of neural program synthesis by integrating partial environmental observations. By utilizing both the environmental context leveraging module and the code symbol alignment module, the ability to rectify semantically erroneous program segments and generalize across various tasks is substantially enhanced. Further- more, we verify that EVAPS exhibits greater resilience when confronted with noise and can adeptly capture subtle features even under more intricate tasks. The proposed approach presents a promising direction for robot program synthesis by incorporating partial environmental observations. The ability of the framework to rectify semantically erroneous program segments, generalize across tasks, and maintain robustness in the presence of noise showcases its potential for practical applications in robot program synthesis.
Acknowledgments and Disclosure of Funding
This work was supported by Shanghai Municipal Science and Technology Major Project (No.20215H22D201003),,
References
[1] Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2 07732, 2021.
[2] Maria Bakhanova and Ilya Makarov. Deep reinforcement learning in vizdoom via dqn and actor-critic agents. In Proceedings of IWANN, 2021.
[3] Matej Balog, Alexander L Gaunt, Mare Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In Proceedings of ICLR, 2017.
[4] Berkay Berabi, Jingxuan He, Veselin Raychev, and Martin Vechev. Tix: Learning to fix coding errors with a text-to-text transformer. In Proceedings of ICML, 2021.
[5] Matko Bošnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian Riedel. Programming with a differentiable forth interpreter. In Proceedings of ICML, 2017.
10

---

[6] Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In Proceedings of ICLR, 2022.
[7] Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh, and Pushmeet Kohli. Lever- aging grammar and reinforcement learning for neural program synthesis. In Proceedings of ICI.R, 2018.
[8] Rudy R Bunel, Alban Desmaison, Pawan K Mudigonda, Pushmeet Kohli, and Philip Torr. Adaptive neural compilation. In Proceedings of NeurlPS, 2016.
[9] Xinyun Chen, Chang Liu, and Dawn Song. Execution- guided neural program synthesis. In Proceedings of ICLR, 2019.
[10] Xinyun Chen, Dawn Song, and Yuandong Tian. Latent execution for neural program synthesis beyond domain-specift. languages. In Proceedings of NeurlPS, 2021.
[1I] Raphaël Dang-Nhu. Plans: Neuro-symbolic program learning from videos. In Proceedings of NeurIPS, 2020.
[12] Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli. Neural program meta-induction. In Proceedings of NewrlPS, 2017.
[13] Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. In Proceedings of ICML, 2017.
[14] Xuguang Duan, Qi Wu, Chuang Gan, Yiwei Zhang. Wenbing Huang, Anton Van Den Hengel, and Wenwu Zhu. Watch, reason and code: Learning to represent videos using program. In Proceedings of ACM MM, 2019.
[15] Majed El Helou and Sabine Süsstrunk. Blind universal bayesian image denoising with gaussian noise level learning. IEEE Transactions on Image Processing, 2020.
[16] Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with a repl. In Proceedings of NeurIPS, 2019.
[17] Kevin Ellis, Daniel Ritchie, Armando Solar-Lezama, and Josh Tenenbaum. Learning to infer graphics programs from hand-drawn images. In Proceedings of NeurlPS, 2018.
[18] Abhay Garg, Anand Sriraman, Kunal Pagarey, and Shirish Karande. Are transformers all that karel needs? In Proceedings of NeurlPS Workshop, 2021.
[19] Kavi Gupta, Peter Ebert Christensen, Xinyun Chen, and Dawn Song. Synthesize, execute and debug: Learning to repair for neural program synthesis. In Proceedings of NeurlPS, 2020.
[20] Jinru Hua, Mengshi Zhang, Kaiyuan Wang, and Sarfraz Khurshid. Towards practical program repair with on-demand candidate generation. In Proceedings of ICSE, 2018.
[21] Justin Huang, Dieter Fox, and Maya Cakmak. Synthesizing robot manipulation programs from a single observed human demonstration. In Proceedings of IROS, 2019.
[22] Jeevana Priya Inala, Chenglong Wang, Mei Yang, Andres Codas, Mark Encarnación, Shuvendu Lahiri, Madanlal Musuvathi, and Jianfeng Gao. Fault-aware neural code rankers. In Proceedings of NeurlPS, 2022.
[23] Naman Jain, Skanda Vaidyanath, Arun Iyer, Nagarajan Natarajan, Suresh Parthasarathy, Sriram Rajamani, and Rahul Sharma. Jigsaw: Large language models meet program synthesis. In Proceedings of ICSE, 2022.
[24] Michal Kempka, Marek Wydmuch, Grzegorz Runc, Jakub Toczek, and Wojciech Jaskowski. Vizdoom: A doom-based ai research platform for visual reinforcement learning. In Proceedings of CIG, 2016.
[25] Adil Khan, Muhammad Naeem, Muhammad Zubair Asghar, Aziz Ud Din, and Atif Khan. Playing first-person shooter games with machine learning techniques and methods using the vizdoom game-ai research platform. Entertainment Computing, 2020.
[26] Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy S Liang. Spoc: Search-based pseudocode to code. In Proceedings of NeurlPS, 2019.
[27] Miguel imitation: Zero-shot task transfer on robots by learning concepts as cognitive programs. Science Robotics, 2019.
Dianhuan Lin, J Swaroop Guntupalli, and Dileep George. Beyond
11

---

[28] Hung Le. Yue Wang, Akhilesh Deepak Gotmare. Silvio Savarese, and Steven Chu Hong Hoi. Coderl: Mastering code generation through pretrained models and deep reinforcement learning. In Proceedings of NeurlPS, 2022.
[29] Xuan-Bach D Le, Duc-Hiep Chu, David Lo. Claire Le Goues, and Willem Visser. S3: syntax- and semantic-guided repair synthesis via programming by examples. In Proceedings of ESEC, 2017.
[30] Claire Le Goues, Michael Dewey-Voge Vogt, Stephanie Forrest, and Westley Weimer, A systematic study of automated program repair: Fixing 55 out of 105 bugs for S8 each. In Proceedings of ICSE, 2012.
[31] Claire Le Goues, Thanh Vu Nguyen, Stephanie Forrest, and Westley Weimer. Genprog: A generic method for automatic software repair. leee transactions on software engineering, 2011.
[32] Wang Ling, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiský, Andrew Senior, Fumin Wang, and Phil Blunsom. Latent predictor networks for code generation. In Proceedings of ACI,, 2016.
[33] Fan Long and Martin Rinard. Automatic patch generation by learning correct code. In Proceedings of POPI. 2016.
[34] Zohar Manna and Richard J Waldinger. Toward automatic program synthesis. Communications of the ACM, 1971.
[35] Hoang Duong Thien Nguyen, Dawei Qi, Abhik Roychoudhury, and Satish Chandra. Semfix: Program repair via semantic analysis. In Proceedings of ICSE, 2013.
[36] Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama. Learning to infer program sketches. In Proceedings of ICML, 2019.
[37] Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. In Proceedings of ICLR, 2017.
[38] Oleksandr Polozov and Sumit Gulwani. Flashmeta: A framework for inductive program synthesis. In Proceedings of OOPSLA, 2015.
[39] Reudismam Rolim, Gustavo Soares, Rohit Gheyi, Titus Barik, and Loris D' Antoni. Learning quick fixes from code repositories. arXiv preprint arXiv: 03806, 2018.
[40] Eric Schkufza, Rahul Sharma, and Alex Aiken. Stochastic superoptimization. ACM SIGARCH Computer Architecture News, 2013.
[41] Kun Shao, Dongbin Zhao, Nannan Li, and Yuanheng Zhu. Learning battles in vizdoom via deep reinforcement learning. In CIG, 2018.
[42] Lin Shao, Toki Migimatsu, Qiang Zhang, Karen Yang, and Jeannette Bohg. Concept2robot: Learning manipulation concepts from instructions and human demonstrations. The International Journal of Robotics Research, 2021.
[43] Eui Chul Shin, Illia Polosukhin, and Dawn Song. Improving neural program synthesis with inferred execution traces. In Proceedings of NeurlPS, 2018
[44] Richard Shin, Neel Kant, Kavi Gupta, Chris Bender, Brandon Trabucco, Rishabh Singh, and Dawn Song. Synthetic datasets for neural program synthesis. In Proceedings of ICLR, 2019.
[45] Richard Shin, Illia Polosukhin, and Dawn Song. Towards specification-diretted program repair. In Proceedings of ICLR Workshop, 2018
[46] Disha Shrivastava, Hugo Larochelle, and Daniel Tarlow. Learning to combine per-example solutions for neural program synthesis. In Proceedings of NeurlPS, 2021.
[47] Shao-Hua Sun, Hyeonwoo Noh, Sriram Somasundaram, and Joseph Lim. Neural program synthesis from diverse demonstration videos. In Proceedings of ICMI,, 2018.
[48] Dweep Trivedi, Jesse Zhang, Shao- Sun, and Joseph J Lim. Learning to synthesize programs as interpretable and generalizable policies. In Proceedings of NewrIPS, 2021.
[49] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of NeurIPS, 2017.
[50] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In Proceedings of ICLR, 2018
12

---

[51] Chenglong Wang. Alvin Cheung, and Rastislav Bodik. Synthesizing highly expressive sql queries from input- examples. In Proceedings of PLDI, 2017.
[52] Ke Wang, Rishabh Singh, and Zhendong Su. Dynamic neural program embeddings for program repair. In Proceedings of ICLR, 2018.
[53] Marek Wydmuch, Michat Kempka, and Wojciech Jaskowski. Vizdoom competitions: Playing doom from pixels. IEEE Transactions on Games, 2019.
[54] He Ye. Matias Martinez, and Martin Monperrus. Neural program repair with execution based backpropagation. In Proceedings of ICSE, 2022.
[55] Haiyan Yin, Jianda Chen, Sinno Jialin Pan, and Sebastian Tschiatschek. Sequential generative exploration model for partially observable reinforcement learning. In Proceedings of AAAI, 2021.
[56] Amit Zohar and Lior Wolf. Automatic program synthesis of long programs with a learned garbage collector. In Proceedings of NeurIPS, 2018.
13


Reviews:
[{"review_id": "Tb9A4FD0mu", "reviewer": "Reviewer_ivtK", "summary": "This paper proposes an approach for program synthesis in robotic domains where the environment context can provide valuable insight for what the correct program should be. The approach takes candidate programs, executes them to get a trace of observations, and then passes the program and trace through a combination of local and global feature extraction with neural networks. The output is a refined program. The approach is trained and tested on randomly generated Vizdoom programs and is substantially better than the alternatives. They also have an ablation study for the contribution of the two types of feature extraction and a study of the approach's noise tolerance.", "questions": "Can SOTA approaches on Karel be applied to Vizdoom? If so, how do they compare? It seems like the intuitive reason this approach works is similar to the idea behind execution-guided synthesis work applied to Karel, so that could be a good comparison to include.\n\nWhere do the program candidates come from before refinement? I don't recall the paper explaining this. This is a big confusion of mine.\n\nI would prefer to have the description of the Vizdoom domain in the evaluation section rather than the preliminary. A figure showing an example task would be helpful too.", "limitations": "N/A", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The results are good. The description of the approach is very clear and easy to understand. Some details are missing but overall it's clear. Vizdoom seems like a popular domain and their approach performs much better than the tested alternatives. \n\nThe introduction does a great job of describing the intuition behind incorporating observation feedback into the program proposal.\n\nI don't have a lot to say about the paper. It is mostly a standard type of paper of applying a new, well-thought out approach to an existing domain. The approach seems sound and the results are good. The main insight is incorporating the environmental feedback to improve the program, which is similar to execution-guided synthesis.", "weaknesses": "The paper doesn't have any glaring weaknesses. As usual, it could be strengthened by applying the approach to another benchmark. \n\nMy main concern is that the gist of the idea seems very similar to work on execution-guided synthesis. But, the approach is shown to be much better than SED on the vizdoom benchmark, so there must be something more here.\n\n# Addressing rebuttal\nI have read the authors rebuttal. In particular, they satisfactorily address my main concern about similarity to other work, which I have no further concerns about.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your meticulous review of our paper and for acknowledging our contribution.\nPlease see below our responses to your comments.\n\n---\n\n> Can SOTA approaches on Karel be applied to Vizdoom?\n\n> My main concern is that the gist of the idea seems very similar to work on execution-guided synthesis.\n\nIn general, approaches on the Karel domain can be applied to the Vizdoom domain. \nWe conducted a review of robotic program synthesis works published in the recent 5 years and identified SED [1] proposed in 2020 as the SOTA approach, which we have evaluated in the paper.\n\nHowever, there exist significant distinctions between SED and our approach:\n\n- SED's execution feedback relies on a global perspective, which is only available in some special cases. In contrast, our approach embraces partial observation, which is more achievable in the real world.\n\n- SED treats the program as a whole for training while our approach pays more attention to the execution context.\n\n- Our approach establishes a connection between the program execution context and the partial observable environment and this connection significantly enhances the performance of our approach.\n\n\n> Where do the program candidates come from before refinement? \n\nIn lines 63-64, we have mentioned that \"*EVAPS initially obtains candidate programs through existing synthesizers*\".\nSpecifically, the candidate programs used in the paper are generated by the same approach used in SED.\nWe will elaborate more in the revision.\n\n> I would prefer to have the description of the Vizdoom domain in the evaluation section rather than the preliminary. A figure showing an example task would be helpful too.\n\nThank you for your suggestion, we will revise the manuscript following your suggestion.\n\n\nReferences\n\n[1] Gupta K, Christensen P E, Chen X, et al. \"Synthesize, execute and debug: Learning to repair for neural program synthesis\". In Proceedings of NeurIPS, 2020."}, {"review_id": "aKkC0ilHKI", "reviewer": "Reviewer_emor", "summary": "The paper proposes Environmental-context Validated lAtent Program Synthesis framework (EVAPS). a program synthesis model that generates executable program for robotic programming, evaluated in the vizdoom environment. It initially obtains candidate programs using other available synthesizers, then performs program repair by executing the candidate program and collect resulted partial environmental observations. It outperfoms a range of prior works for viszoom program synthesis, and demonstrated robustness again observation noises and task complexity.", "questions": "see weeknesses.", "limitations": "The major limitation i see in this framework is the assumption of aqcuiring partial observations and executing program candidates in the environment. These assumption is not valid in real-world real-time control. More justifications on this would be very helpful.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- using the aid of partially observed environments for program synthesis and repair is novel and reasonable\n- the proposed framework is sound, and the design choices for utilizing observations, and using a graph structure to aggregate environmental and syntactic information flow is convincing\n- extensive experiments", "weaknesses": "- the writing of the paper can be improved, by reducing repetitive and inconsistent adjectives\n- do the baselines use program repair? Does any of them rely on environmental observations?\n- the assumption of executing candidate programs makes more sense when a privileged simulation environment is available, and when real-time control is not needed. Can the author provide further justification regarding this? How would you expect to transfer to real world?\n- the author claim that EVAPS shows is more robust agains noise in the conclusion, but there's no comparison with baseline  on this matter in the experiment section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your constructive comments. We address your comments in the following.\n\n> Writing of the paper can be improved\n\nThanks for your comments. We will proofread the manuscript carefully.\n\n> Do the baselines use program repair? Does any of them rely on environmental observations?\n\nIn baselines, SED [1] uses execution feedback to fix the program. It first produces initial programs using the neural program synthesizer component, then utilizes a neural program debugger to iteratively repair the generated programs. SED also uses environmental observation for training the neural program debugger.\n\nHowever, there exist significant distinctions between SED and our approach: \n- SED's execution feedback relies on a global perspective, which is only available in some special cases. In contrast, our approach embraces partial observation, which is more achievable in the real world.\n\n- SED treats the program as a whole for training while our approach pays more attention to the execution context.\n\n- Our approach establishes a connection between the program execution context and the partial observable environment and this connection significantly enhances the performance of our approach.\n\n> How would you expect to transfer to the real world?\n\nThe partial observation that our approach relies on is often available in practice, so it is theoretically feasible to apply our approach to the real world. \nCertainly, we anticipate some practical difficulties during the transition from the simulation environment to the real world. It is labor-intensive to collect enough training environment data from the real world.\n\n\n> The author claim that EVAPS shows is more robust against noise in the conclusion, but there's no comparison with the baseline on this matter in the experiment section.\n\nTo clarify, we are not evaluating if EVAPS achieves better robustness over other baselines. Instead, we aim to evaluate how EVAPS performs in an environment with noise. The result shows that our approach demonstrates relatively good robustness.\n\n\nReference\n\n[1] Gupta K, Christensen P E, Chen X, et al. \"Synthesize, execute and debug: Learning to repair for neural program synthesis\". In Proceedings of NeurIPS, 2020."}, {"review_id": "nUXFwQEz7e", "reviewer": "Reviewer_2nvQ", "summary": "This paper proposes EVAPS to enhance robotic program synthesis by integrating parietal environmental observations. Specifically, EVAPS utilizes both the environmental context leveraging module and the code symbol alignment module to improve its ability to rectify semantically erroneous program segments and generalize across various tasks. Comprehensive experiments on the partially observed Vizdoom benchmark demonstrate its superior performance over other baselines across various tasks. Overall, this is a well-written paper and its extensive experiments and ablation studies verify the effectiveness of the proposed method. I would be leaning to accept this paper.", "questions": "Can you shed some light on the limitations of the proposed method? ", "limitations": "This paper just discussed the limitations very lightly. I would like to see more discussion on its limitations.", "rating": 6, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* The proposed method is technically sound and well motivated.\n* This paper is well written and well structured. It provides clear formulations and an overview figure to well explain the method.\n* The experimental evaluation is rather comprehensive and provides convincing results to demonstrate the effectiveness of the proposed method.\n", "weaknesses": " I did not identify any weaknesses for this paper as I am not familiar with the task of robotic program synthesis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for acknowledging our contributions. We address your comments in the following.\n\n> Limitation\n\nSince our approach is based on self-supervised training, it relies on the quality of the data used for training. \nHowever, data quality is a common issue in this field.\n\nMoreover, we anticipate some practical difficulties during the transition from the simulation environment to the real world. It is labor-intensive to collect enough training environment data from the real world."}, {"review_id": "kdBedwqqai", "reviewer": "Reviewer_wkgC", "summary": "The paper claims that global observation in robot program synthesis is not achievable, so it proposes to use partial observation. And it learns an observation embedding module and a semantic-grammatical alignment module to repair the candidate programs that can increase the accuracy and generalization of robot program synthesis.", "questions": "Please see weaknesses. ", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "1. The problem this paper focused on is important to the application of PS as the perfect and complete observable environment is often not available in the real world.\n\n2. The experiment setting and analysis are clear and comprehensive. The paper analyses the effect of multiple aspects factors in the in-perfect observation of the proposed method. ", "weaknesses": "[W1]. The key weakness is the choice of baseline methods. As a program repair method, it’s better to compare with methods that have a fair setting rather than program generation methods. There are other program repair methods that utilize trajectory to enhance performance. Moreover, the baseline methods are too old (most before 2020).\n\n[1] Execution-guided neural program synthesis\n\n[2] Write, execute, assess: Program synthesis with a REPL\n\n[2] Improving neural program synthesis with inferred execution traces\n\n\n[W2]. Needs more explanation about the difference between global environment information and partially observable environments. \n\n[W2.1] As using pre-observation and post-observation which are related to specific program segments to enhance the information contained in the embedding is a general trick. The PS methods which take global environment information as input can also learn such representation to enhance accuracy and generalization. What is the key connection between the proposed method and partially observable environments? \n\n[W2.2] Needs some insightful evaluation in the results section to demonstrate the relation between the main motivation (partial observable environment) and the proposed architecture.\n\n[W3]. There are some typos, like line 203, citation 41 is not the baseline", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful comments and constructive suggestions. We summarise the issues pointed out and address them in the following:  \n\n---\n\n> Choice of baseline\n\nWe conducted a review of robotic program synthesis works published in the recent 5 years and identified SED proposed in 2020 as the state-of-the-art technique in robotic program synthesis. In the evaluation, we compared our approach with SED as shown in Section 4.2. The experiment results show our approach significantly outperforms SED.\n\nRegarding traditional program repair approaches, we are indeed aware of a branch of rich works in the program repair area, which can be classified into three categories:\n- Search-based. This type of approach considers program repair as a search problem, exploring the space of all possible program candidates to identify one that satisfies the given weak specification, i.e., test cases. The representative work of this area is GenProg [1].\n- Semantic-based. This type of approach extracts semantic information from the program under repair (typically represented as path constraints) and then generates patches by solving those constraints. The representative work is SemFix [2].  \n- Learning-based. This type of approach leverages a number of patches generated by developers to learn a model that repairs programs. An earlier and representative work is Prophet [3]. \n\nThose approaches depend on high-quality test suites to validate patch candidates, which are unavailable in the setting our approach is targeted at, i.e., Vizdoom. Besides, Karel and Vizdoom are designed for specific purposes. Complex features in programs that traditional program repair approaches rely on can be abstracted away. These pose challenges for applying traditional program repair approaches to such domains.\nFor these reasons, robotic program synthesis work with a focus on program repair SED [4] also does not have a comparison with traditional program repair approaches.\n\n> More explanation on the difference between global execution environment and partial execution environment\n\nIn the context of robotic systems, \"partial environment\" pertains to the immediate surroundings that the robot is capable of perceiving through its sensory devices, whereas the concept of \"global environment\" encompasses a comprehensive understanding of the entire scenario, including elements beyond the robot's perceptual capabilities [5, 6]. In the real world, global observations are typically unavailable and only partial observations are available. Thus, our approach is focused on partial observations for enhancing program synthesis.\n\n> The key connection between the proposed approach and partially observable environments\n\nThe key connection between the proposed approach and observable environments is our unique design that establishes a connection between the program execution context and the partially observable environment. As shown in lines 127-133, our approach takes the execution context of statement $S$ and the partially observable environment of statement $S$ as a unit for model training. This enables the combination of program syntax and the corresponding partially observable environment to predict a token, thereby enhancing the accuracy of program synthesis.\n\n> Evaluation of the key connection between the proposed approach and partially observable environment\n\nWe conducted a study to evaluate the effectiveness of our design in the experiment. As shown in Table 2, EVAPS achieves the best performance and its performance significantly goes down when the unique design is taken away. “EVAPS+O” and “EVAPS+S” are variants of EVAPS without connecting the program execution context and the partially observable environment and they both underperform EVAPS.\n\n> Typos\n\nThank you for your feedback, we will carefully proofread the manuscript and correct errors pointed out.\n\nReferences\n\n[1] Le Goues, Claire, et al. \"Genprog: A generic method for automatic software repair.\" Ieee transactions on software engineering, 2011.\n\n[2] Nguyen, Hoang Duong Thien, et al. \"Semfix: Program repair via semantic analysis.\" In Proceedings of ICSE, 2013.\n\n[3] Long, Fan, and Martin Rinard. \"Automatic patch generation by learning correct code.\" In Proceedings of POPL, 2016.\n\n[4] Gupta K, Christensen P E, Chen X, et al. \"Synthesize, execute and debug: Learning to repair for neural program synthesis\". In Proceedings of NeurIPS, 2020. \n\n[5] Chen, Ci, et al. \"Motion planning for heterogeneous unmanned systems under partial observation from uav.\" In Proceedings of IROS, 2020.\n\n[6] Katsumata, Yuki, et al. \"Map completion from partial observation using the global structure of multiple environmental maps.\" Advanced Robotics, 2022."}, {"review_id": "r35vP7Xodv", "reviewer": "Reviewer_mJeF", "summary": "\nThis paper introduces the Environmental-context Validated lAtent Program Synthesis framework (EVAPS), which builds upon the SED approach by utilizing a trail-eval-repair loop to enhance program evolution and improve generalization capabilities. EVAPS leverages partial environmental observations by initially obtaining candidate programs from existing synthesizers. By executing these candidate programs and capturing the environmental context before and after each action, EVAPS models both the environmental and syntax contexts concurrently. Through iterative modifications to address semantic conflicts across program tokens, EVAPS aims to correct erroneous program fragments that do not produce the desired output.\n\nThe proposed framework was evaluated in the partially observed Vizdoom domain, involving a robot navigating a 3D world and interacting with various elements, including objects and adversaries. The experiment results demonstrate the superiority of the approach over the baselines in accurately modeling program semantic subtleties and effectively resolving potential errors. ", "questions": "EVAPS seems incremental to SED. To gain a comprehensive understanding of EVAPS' contribution, it would be beneficial to apply the framework to the Karel domain, where the baselines were evaluated. This approach would effectively demonstrate the effectiveness of the observation leveraging module and the code symbol alignment module. Is there any evidence or indication from the authors regarding the performance of EVAPS specifically in the Karel domain?", "limitations": "The paper presents an approach for robot program synthesis. However, the evaluation falls short in providing a convincing argument on how EVAPS can be effectively applied to learn robot-control policies, as the experiments are confined to a relatively simple video game environment. Further investigation and experimentation in more complex and realistic robotic scenarios would be necessary to demonstrate the practical utility and effectiveness of EVAPS in learning robot-control policies.", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ EVAPS synthesizes robot programs operating in partially observed environments (surrounding RGBD image inputs). \n+ EVAPS uses a trail-eval-repair loop to iteratively improve program generalizability by rectifying potentially erroneous code segments.\n+ EVAPS is capable of handling noisy observations.\n\nA key novelty of EVAPS, when compared to previous program synthesis approaches in the Karel domain, is its ability to handle partial environmental observations. This capability is crucial for synthesizing robot programs, as relying on global environment information is often impractical in real-world robot navigation tasks. EVAPS consists of two essential modules: the partial observation leveraging module, which emphasizes the environmental context of specific program tokens, and the code symbol alignment module, which focuses on modeling the implicit connections between different code segments in semantic spaces. By integrating both syntax and semantic information, these modules facilitate program repair and enhance the effectiveness of EVAPS in generating accurate and meaningful robot programs.", "weaknesses": "The title of the paper may appear to overstate the actual contribution made by the research.  The choice of the Vizdoom environment as a benchmark for evaluating Robotic Program Synthesis in this paper raises some concerns. The evaluation of EVAPS in the navigation-focused Vizdoom environment does appear to have limitations. While efficient navigation is undoubtedly an important robotic task, it may not fully represent the diverse range of tasks in robotics, particularly those involving object manipulation in fully observable environments. It would be valuable to explore the applicability of EVAPS in synthesizing robot programs for other more realistic environments like Miniworld and AI2-Thor, which involve long-horizon vision-based tasks. Assessing the performance of EVAPS in such contexts would provide a more comprehensive evaluation of its capabilities. Given the current state of the paper, it remains uncertain whether EVAPS is adequately equipped to handle the challenges posed by complex robotic navigation tasks. To determine the true extent of EVAPS' applicability across a broader range of robotic tasks and environments, additional research and experimentation are necessary.\n\nNevertheless, I do believe this paper contributes to the program synthesis community. The comparative evaluation of EVAPS against the baselines, when provided with partial observations, showcases its superior performance, thereby highlighting the significance of the observation leveraging module and the code symbol alignment module. However, there remains a lingering uncertainty regarding the practical implications of this demonstrated value in the context of robot control. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the insightful comments and constructive suggestions. We summarise the issues pointed out and address them in the following:  \n\n\n> A gap between the title and experiment environment in which this work is evaluated\n\nThanks for pointing this out. In this work,  we explore the topic \"enhancing robotic program synthesis with the execution environment\" and believe that it will complement traditional program synthesis and is worthwhile exploring. Considering navigation is one of the most common and important tasks in robotics, we evaluate our work on navigation tasks in robotics. To be accurate, we will make our paper title specific to navigation tasks in the revision. \n\n> Choice of experiment environments\n\nAs the reviewer pointed out, there exist several commonly used execution environments for evaluating approaches in robotics including Karel, Vizdoom, Miniworld and AI2-Thor. We went through the following process to choose our experiment environment. \n\nWe conducted a review of robotic program synthesis works published in the recent 5 years (the most related works are listed below [1-9]) and found that they use either Karel or Vizdoom as the experiment environment. \n\nIn the end, we chose Vizdoom over Karel as our experiment environment since tasks in Vizdoom involve more actions and scenarios are more complex. The differences between them are shown as follows. Karel is a 2D grid world involving 5 marker actions primitives and 5 perceptions primitives for obstacle detection. Vizdoom is a 3D semi-realistic simulation environment involving 7 interactive action primitives and 6 perception primitives [3]. \n\n|  Environment   | Dimension  | DSL space (action,perception) | State Representation | Task Type\n|  ----  | ----  | ----  | ----  | ----  |\n| Vizdoom | 3D | ( 7 , 6 ) | 120 x 160 x 3 | Navigation |\n| Karel  | 2D | ( 5 , 5 ) | 8 x 8 x 16 | Navigation |\n\nIn general, Vizdoom covers Karel in terms of environmental dimensions, the complexity of state representation as well as action and perception space. Thus, we chose Vizdoom as our execution environment. \n\n> Indication of the performance of our approach in the Karel domain\n\nAs discussed above, Vizdoom is sort of an upgraded version of Karel. Relevant actions and perceptions in Karel are contained in Vizdoom. Most of the scenarios and tasks in Karel can be found in Vizdoom. Since our approach outperforms the baselines in Vizdoom, it is reasonable for us to believe consistent results can be achieved in the Karel domain.\n\nReference \n\n[1] Duan, Xuguang, et al. \"Watch, reason and code: Learning to represent videos using program.\" In Proceedings of  ACM MM, 2019.\n\n[2] Dang-Nhu, Raphaël. \"PLANS: Neuro-symbolic program learning from videos.\" In Proceedings of NeurIPS, 2020.\n\n[3] Sun, Shao-Hua, et al. \"Neural program synthesis from diverse demonstration videos.\" In Proceedings of ICML, 2018.\n\n[4] Gupta K, Christensen P E, Chen X, et al. \"Synthesize, execute and debug: Learning to repair for neural program synthesis\". In Proceedings of NeurIPS, 2020.\n\n[5] Chen, Xinyun, Dawn Song, and Yuandong Tian. \"Latent execution for neural program synthesis beyond domain-specific languages.\" In Proceedings of NeurIPS, 2021.\n\n[6] Manchin, Anthony, et al. \"Program Generation from Diverse Video Demonstrations.\" arXiv preprint arXiv:2302.00178 (2023).\n\n[7] Chen, Xinyun, Chang Liu, and Dawn Song. \"Execution-guided neural program synthesis.\" In Proceedings of ICLR, 2018.\n\n[8] Shin, Eui Chul, Illia Polosukhin, and Dawn Song. \"Improving neural program synthesis with inferred execution traces.\" In Proceedings of NeurIPS, 2018.\n\n[9] Trivedi, Dweep, et al. \"Learning to synthesize programs as interpretable and generalizable policies.\" In Proceedings of NeurIPS, 2021.\n"}]

Author rebuttal:

Meta-review: The paper proposes an approach for program synthesis in robotic domains that extends the traditional programming by example paradigm with an automated repair step that observes the behavior of the synthesized program and proposes a corrected program based on that. 
The idea is original and seems to perform better than a number of state-of-the-art baselines. In particular, the paper builds on prior work on the Synthesize-execute-debug approach from prior program synthesis work, but the experiments show that it performs significantly better. 

The main concern from one of the reviewers was that the paper is oversold in its potential as a robotics contribution, since the tasks are too short for what is considered state-of-the art in robotics. Nevertheless, I think this is a valuable contribution for program synthesis, and a clear improvement over the state-of-the-art.
Decision: Accept (poster)